
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
  <head>
    <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
    <link href='/css/styles.css' rel='stylesheet' type='text/css' />
    <link href='/images/favicon.png' rel='shortcut icon' />
    <script src='/js/jquery.min.1.4.js'></script>
    <script src='/js/app.js'></script>
    <meta content='width=device-width, minimum-scale=1.0, maximum-scale=1.0' name='viewport' />
    <title>Redis 集群规范 -- Redis中文资料站</title>
	<meta http-equiv="description" content="Redis 集群规范文档" />
  </head>
  <body class=''>
    <script src='/js/head.js'></script>
     <div class='text'>
    <article id='topic'>
        <h1>Redis 集群规范 （仍在开发中）</h1>
        <!-- <h1>Redis cluster Specification (work in progress)</h1> -->
        
        <h2>Redis 集群的目标</h2>
        <!-- <h2>Redis Cluster goals</h2> -->

        <p>Redis 集群是 Redis 的一个分布式实现，主要是为了实现以下这些目标（按在设计中的重要性排序）：</p>
        <!-- <p>Redis Cluster is a distributed implementation of Redis with the following goals, in order of importance in the design:</p> -->

        <ul>
        <li>在1000个节点的时候仍能表现得很好并且可扩展性（scalability）是线性的。</li>
        <!-- <li>High performance and linear scalability up to 1000 nodes.</li> -->
        <li>没有合并操作，这样在 Redis 的数据模型中最典型的大数据值中也能有很好的表现。</li>
        <!-- <li>No merge operations in order to play well with the large values typical of the Redis data model.</li> -->
        <li>写入安全（Write safety）：那些与大多数节点相连的客户端所做的写入操作，系统尝试全部都保存下来。不过公认的，还是会有小部分（small windows?）写入会丢失。</li>
        <!-- <li>Write safety: the system tries to retain all the writes originating from clients connected with the majority of the nodes. However there are small windows where acknowledged writes can be lost.</li> -->
        <li>可用性（Availability）：在绝大多数的主节点（master node）是可达的，并且对于每一个不可达的主节点都至少有一个它的从节点（slave）可达的情况下，Redis 集群仍能进行分区（partitions）操作。
        <!-- <li>Availability: Redis Cluster is able to survive to partitions where the majority of the master nodes are reachable and there is at least a reachable salve for every master node that is no longer reachable.</li> -->
        </ul>
        
        <p>这篇文档要讲的是，在 Redis 仓库（放在Github上）中的 <code>unstable</code> 分支中实现的功能。</p>
        <!-- <p>What is described in this document is implemented in the <code>unstable</code> branch of the Github Redis repository.</p> -->

        <h2>实现的功能子集</h2>
        <!-- <h2>Implemented subset</h2> -->

        <p>Redis 集群实现了所有在非分布式 Redis 版本中出现的处理单一键值（key）的命令。那些使用多个键值的复杂操作，
        比如 set 里的并集（unions）和交集（intersections）操作，就没有实现。通常来说，那些处理命令的节点获取不到键值的所有操作都不会被实现。</p>
        <!-- <p>Redis Cluster implements all the single keys commands available in the
        non distributed version of Redis. Commands performing complex multi key
        operations like Set type unions or intersections are not implemented, and in
        general all the operations where keys are not available in the node processing
        the command are not implemented.</p> -->

        <p>在将来，用户或许可以通过使用 <code>MIGRATE COPY</code> 命令，在集群上用 <em>计算节点（Computation Nodes）</em> 来执行多键值的只读操作，
        但 Redis 集群本身不会执行复杂的多键值操作来把键值在节点间移来移去。</p>
        <!-- <p>In the future it is possible that using the <code>MIGRATE COPY</code> command users will
        be able to use <em>Computation Nodes</em> to perform multi-key read only operations
        in the cluster, but it is not likely that the Redis Cluster itself will be
        able to perform complex multi key operations implementing some kind of
        transparent way to move keys around.</p> -->

        <p>Redis 集群不像单机版本的 Redis 那样支持多个数据库，集群只有数据库 0，而且也不支持 <a href="/commands/select.html">SELECT</a> 命令。</p>
        <!-- <p>Redis Cluster does not support multiple databases like the stand alone version
        of Redis, there is just database 0, and <a href="/commands/select.html">SELECT</a> is not allowed.</p> -->

        <h2>Redis 集群协议中的客户端和服务器端</h2>
        <!-- <h2>Clients and Servers roles in the Redis cluster protocol</h2> -->

        <p>在 Redis 集群中，节点负责存储数据、记录集群的状态（包括键值到正确节点的映射）。集群节点同样能自动发现其他节点，检测出没正常工作的节点，
        并且在需要的时候在从节点中推选出主节点。</p>
        <!-- <p>In Redis cluster nodes are responsible for holding the data,
        and taking the state of the cluster, including mapping keys to the right nodes.
        Cluster nodes are also able to auto-discover other nodes, detect non working
        nodes, and performing slave nodes election to master when needed.</p> -->

        <p>为了执行这些任务，所有的集群节点都通过TCP连接（TCP bus？）和一个二进制协议（集群连接，<strong>cluster bus</strong>）建立通信。
        每一个节点都通过集群连接（cluster bus）与集群上的其余每个节点连接起来。节点们使用一个 gossip 协议来传播集群的信息，这样可以：发现新的节点、
        发送ping包（用来确保所有节点都在正常工作中）、在特定情况发生时发送集群消息。集群连接也用于在集群中发布或订阅消息。</p>
        <!-- <p>To perform their tasks all the cluster nodes are connected using a
        TCP bus and a binary protocol (the <strong>cluster bus</strong>).
        Every node is connected to every other node in the cluster using the cluster
        bus. Nodes use a gossip protocol to propagate information about the cluster
        in order to discover new nodes, to send ping packets to make sure all the
        other nodes are working properly, and to send cluster messages needed to
        signal specific conditions. The cluster bus is also used in order to
        propagate Pub/Sub messages across the cluster.</p> -->

        <p>由于集群节点不能代理（proxy）请求，所以客户端在接收到重定向错误（redirections errors） <code>-MOVED</code> 和 <code>-ASK</code> 的时候，
        将命令重定向到其他节点。理论上来说，客户端是可以自由地向集群中的所有节点发送请求，在需要的时候把请求重定向到其他节点，所以客户端是不需要保存集群状态。
        不过客户端可以缓存键值和节点之间的映射关系，这样能明显提高命令执行的效率。</p>
        <!-- <p>Since cluster nodes are not able to proxy requests clients may be redirected
        to other nodes using redirections errors <code>-MOVED</code> and <code>-ASK</code>.
        The client is in theory free to send requests to all the nodes in the cluster,
        getting redirected if needed, so the client is not required to take the
        state of the cluster. However clients that are able to cache the map between
        keys and nodes can improve the performance in a sensible way.</p> -->

        <h2>安全写入</h2>
        <!-- <h2>Write safety</h2> -->

        <p>Redis 集群节点间使用异步冗余备份（asynchronous replication），所以在分区过程中总是存在一些时间段（windows？），在这些时间段里容易丢失写入数据。
        但是一个连接到绝大部分主节点的客户端的时间段，与一个连接到极小部分主节点的客户端的时间段是相当不同的。</p>
        <!-- <p>Redis Cluster uses asynchronous replication between nodes, so there are always windows when it is possible to lose writes during partitions. However these windows are very different in the case of a client that is connected to the majority of masters, and a client that is connected to the minority of masters.</p> -->
        
        <p>Redis 集群会努力尝试保存所有与大多数主节点连接的客户端执行的写入，但以下两种情况除外：</p>
        <!-- <p>Redis Cluster tries hard to retain all the writes that are performed by clients connected to the majority of masters, with two exceptions:</p> -->

        <p>1) 一个写入操作能到达一个主节点，但当主节点要回复客户端的时候，这个写入有可能没有通过主从节点间的异步冗余备份传播到从节点那里。
        如果在某个写入操作没有到达从节点的时候主节点已经宕机了，那么该写入会永远地丢失掉，以防主节点长时间不可达而它的一个从节点已经被提升为主节点。</p>
        <!--<p>1) A write may reach a master, but while the master may be able to reply to the client, the write may not be propagated to slaves via the asynchronous replication used between master and slave nodes. If the master dies without the write reaching the slaves, the write is lost forever in case the master is unreachable for a long enough period that one of its slaves is promoted.</p>-->
        
        <p>2) 另一个理论上可能会丢失写入操作的模式是：</p>
        <!-- <p>2) Another theoretically possible failure mode where writes are lost is the following:</p> -->
        
        <ul>
        <li>因为分区使一个主节点变得不可达。</li>
        <!-- <li>A master is unreachable because of a partition.</li> -->
        <li>故障转移（fail over）到主节点的一个从节点。（即从节点被提升为主节点）</li>
        <!-- <li>It gets failed over by one of its slaves.</li> -->
        <li>过一段时间之后主节点再次变得可达。</li>
        <!-- <li>After some time it may be reachable again.</li> -->
        <li>一个没有更新路由表（routing table）的客户端或许会在集群把这个主节点变成一个从节点（新主节点的从节点）之前对它进行写入操作。</li>
        <!-- <li>A client with a not updated routing table may write to it before the master is converted to a slave (of the new master) by the cluster.</li> -->
        </ul>
        
        <p>实际上这是极小概率事件，这是因为，那些由于长时间无法被大多数主节点访问到的节点会被故障转移掉，不再接受任何写入操作，当其分区修复好以后仍然会在一小段时间内拒绝写入操作好让其他节点有时间被告知配置信息的变更。通常所有节点都会尝试通过非阻塞连接尝试（non-blocking connection attempt）尽快去访问一个再次加入到集群里的节点，一旦跟该节点建立一个新的连接就会发送一个ping包过去（这足够升级节点配置信息）。这就使得一个节点很难在恢复可写入状态之前没被告知配置信息更改。</p>
        <!-- <p>Practically this is very unlikely to happen because nodes not able to reach the majority of other masters for enough time to be failed over, no longer accept writes, and when the partition is fixed writes are still refused for a small amount of time to allow other nodes to inform about configuration changes. All the nodes in general try to reach a node that joins the cluster again as fast as possible, using a non-blocking connection attempt and sending a ping packet (that is enough to upgrade the node configuration) as soon as there is a new link with the node. This makes unlikely that a node is not informed about configuration changes before it returns writable again.</p> -->
        
        <p>Redis 集群在拥有少数主节点和至少一个客户端的分区上容易丢失为数不少的写入操作，这是因为如果主节点被故障转移到集群中多数节点那边的节点上，
        那么所有发送到这些主节点的写入操作都会永久性丢失。</p>
        <!-- <p>Redis Cluster loses a non trivial amount of writes on partitions where there is a minority of masters and at least one or more clients, since all the writes sent to the masters may potentially get lost if the masters are failed over in the majority side.</p> -->
        
        <p>一个主节点要被故障转移，必须是大多数主节点在至少 <code>NODE_TIMEOUT</code> 这么长时间里无法访问该节点，所以如果分区在这段时间之前修复好了，就没有写入操作会丢失。当分区故障持续超过 <code>NODE_TIMEOUT</code>，集群的多数节点这边会在一超过 <code>NODE_TIMEOUT</code> 这个时间段后开始拒绝往受损分区进行写入，所以在少数节点这边（指分区）变得不再可用后，会有一个写入操作最大损失范围（因为在指定时间段后将不会再有写入操作被接收或丢失）。</p>
        <!-- <p>For a master to be failed over, it must be not reachable by the majority of masters for at least <code>NODE_TIMEOUT</code>, so if the partition is fixed before that time, no write is lost. When the partition lasts for more than <code>NODE_TIMEOUT</code>, the minority side of the cluster will start refusing writes as soon as <code>NODE_TIMEOUT</code> time has elapsed, so there is a maximum window after which the minority becomes no longer available, hence no write is accepted and lost after that time.</p> -->
        
        <h2>可用性</h2>
        <!-- <h2>Availability</h2> -->
        
        <p>Redis 集群在分区的少数节点那边不可用。集群假设在分区的多数节点这边至少有大多数可达的主节点，并且对于每个不可达主节点都至少有一个从节点可达，在经过了差不多 <code>NODE_TIMEOUT</code> 这么长时间后，有个从节点被推选出来并故障转移掉它的主节点，这时集群又再恢复可用。</p>
        <!-- <p>Redis Cluster is not available in the minority side of the partition. In the majority side of the partition assuming that there are at least the majority of masters and a slave for every unreachable master, the cluster returns available after <code>NODE_TIMEOUT</code> plus some more second required for a slave to get elected and failover its master.</p> -->
        
        <p>这意味着 Redis 集群的设计是能容忍集群中少数节点的出错，但对于要求大量网络分块（large net splits）的可用性的应用来说，这并不是一个合适的解决方案。</p>
        <!-- <p>This means that Redis Cluster is designed to survive to failures of a few nodes in the cluster, but is not a suitable solution for applications that require availability in the event of large net splits.</p> -->
        
        <p>举个例子，一个由 N 个主节点组成的集群，每个主节点都只有一个从节点。当有一个节点（因为故障）被分割出去后，集群的多数节点这边仍然是可访问的。当有两个节点（因故障）被分割出去后集群仍可用的概率是 <code>1-(1/(N*2-1))</code>（在第一个节点故障出错后总共剩下 <code>N*2-1</code> 个节点，那么失去冗余备份（即失去从节点）的那个主节点也故障出错的概率是 <code>1/(N*2-1))</code>）。</p>
        <!-- <p>In the example of a cluster composed of N master nodes where every node has a single slave, the majority side of the cluster will remain available as soon as a single node is partitioned away, and will remain available with a probability of <code>1-(1/(N*2-1))</code> when two nodes are partitioned away (After the first node fails we are left with <code>N*2-1</code> nodes in total, and the probability of the only master without a replica to fail is <code>1/(N*2-1))</code>.</p> -->
        
        <p>比如一个拥有5个节点的集群，每个节点都只有一个从节点，那么在两个节点从多数节点这边分割出去后集群不再可用的概率是 <code>1/(5*2-1) = 0.1111</code>，即有大约 11% 的概率。</p>
        <!-- <p>For example in a cluster with 5 nodes and a single slave per node, there is a <code>1/(5*2-1) = 0.1111</code> probabilities that after two nodes are partitioned away from the majority, the cluster will no longer be available, that is about 11% of probabilities.</p> -->
        
        <h2>表现</h2>
        <!-- <h2>Performance</h2> -->
        
        <p>在 Redis 集群中节点并不是把命令转发到管理所给出的键值的正确节点上，而是把客户端重定向到服务一定范围内的键值的节点上。
        最终客户端获得一份最新的集群表示，里面有写着哪些节点服务哪些键值子集，所以在正常操作中客户端是直接联系到对应的节点并把给定的命令发过去。</p>
        <!-- <p>In Redis Cluster nodes don&#39;t proxy commands to the right node in charge for a given key, but instead they redirect clients to the right nodes serving a given range of the key space.
        Eventually clients obtain an up to date representation of the cluster and which node serves which subset of keys, so during normal operations clients directly contact the right nodes in order to send a given command.</p> -->
        
        <p>由于使用了异步冗余备份，节点不会等待其他节点对写入操作的承认。（目前正在开发可选同步冗余备份，极有可能会添加入将来的代码发布中）</p>
        <!-- <p>Because of the use of asynchronous replication, nodes does not wait for other nodes acknowledgment of writes (optional synchronous replication is a work in progress and will be likely added in future releases).</p> -->
        
        <p>同样，由于一些命令不支持操作多个键值，如果不是碎片重整（resharding），那么数据是永远不会在节点间移动的。</p>
        <!-- <p>Also, because of the restriction to the subset of commands that don&#39;t perform operations on multiple keys, data is never moved between nodes if not in case of resharding.</p> -->
        
        <p>所以普通操作是可以被处理得跟在单一 Redis 上一样的。这意味着，在一个拥有 N 个主节点的 Redis 集群中，由于 Redis 的设计是支持线性扩展的，所以你可以认为同样的操作在集群上的表现会跟在单一 Redis 上的表现乘以 N 一样。同时，询问（query）通常在一次循环中被执行，客户端会保持跟节点持续不断的连接，所以延迟数据跟在单一 Reids 上是一样的。</p>
        <!-- <p>So normal operations are handled exactly as in the case of a single Redis instance. This means that in a Redis Cluster with N master nodes you can expect the same performance as a single Redis instance multiplied by N as the design allows to scale linearly. At the same time the query is usually performed in a single round trip, since clients usually retain persistent connections with the nodes, so latency figures are also the same as the single stand alone Redis node case.</p> -->
        
        <h2>为什么要避免使用合并操作</h2>
        <!-- <h2>Why merge operations are avoided</h2> -->
        
        <p>Redis 集群的设计是避免在多个节点中存在同个键值对的冲突版本，这是因为 Redis 数据模型并不提倡这么做：Redis 中的值通常都是比较大的，经常可以看到列表或者排序好的集合中有数以百万计的元素。数据类型也是语义复杂的。传输和合并这样的值将会变成一个主要的性能瓶颈。</p>
        <!-- <p>Redis Cluster design avoids conflicting versions of the same key-value pair in multiple nodes since in the case of the Redis data model this is not always desirable: values in Redis are often very large, it is common to see lists or sorted sets with millions of elements. Also data types are semantically complex. Transferring and merging these kind of values can be a major bottleneck.</p> -->
        
        <h2>键分布模型</h2>
        <!-- <h2>Keys distribution model</h2> -->
        
        <p>键空间被分割为 16384 槽（slot），事实上集群的最大节点数量是 16384 个。（然而建议最大节点数量设置在1000这个数量级上）</p>
        <!-- <p>The key space is split into 16384 slots, effectively setting an upper limit
        for the cluster size of 16384 nodes (however the suggested max size of
        nodes is in the order of ~ 1000 nodes).</p> -->
        
        <p>所有的主节点都负责 16384 个哈希槽中的一部分。当集群处于<strong>稳定</strong>状态时，集群中没有在执行重配置（reconfiguration）操作，每个哈希槽都只由一个节点进行处理（不过主节点可以有一个或多个从节点，可以在网络断线或节点失效时替换掉主节点）。</p>
        <!-- <p>All the master nodes will handle a percentage of the 16384 hash slots.
        When the cluster is <strong>stable</strong>, that means that there is no a cluster
        reconfiguration in progress (where hash slots are moved from one node
        to another) a single hash slot will be served exactly by a single node
        (however the serving node can have one or more slaves that will replace
        it in the case of net splits or failures).</p> -->
        
        <p>以下是用来把键映射到哈希槽的算法（下一段哈希标签例外就是按照这个规则）：</p>
        <!-- <p>The base algorithm used to map keys to hash slots is the following
        (read the next paragraph for the hash tag exception to this rule):</p> -->
        
        <pre><code>HASH_SLOT = CRC16(key) mod 16384&#x000A;</code></pre>
        
        <p>其中，CRC16的定义如下：</p>
        <!-- <p>The CRC16 is specified as follows:</p> -->
        
        <ul>
        <li>名称：XMODEM（也可以称为 ZMODEM 或 CRC-16/ACORN）</li>
        <!-- <li>Name: XMODEM (also known as ZMODEM or CRC-16/ACORN)</li> -->
        <li>输出长度：16 bit</li>
        <!-- <li>Width: 16 bit</li> -->
        <li>多项数（poly）：1021（即是 x<sup>16</sup> + x<sup>12</sup> + x<sup>5</sup> + 1 ）</li>
        <!-- <li>Poly: 1021 (That is actually x<sup>16</sup> + x<sup>12</sup> + x<sup>5</sup> + 1)</li> -->
        <li>初始化：0000</li>
        <!-- <li>Initialization: 0000</li> -->
        <li>反射输入字节（Reflect Input byte）：False</li>
        <!-- <li>Reflect Input byte: False</li> -->
        <li>反射输入CRC（Reflect Output CRC）：False</li>
        <!-- <li>Reflect Output CRC: False</li> -->
        <li>用于输出CRC的异或常量（Xor constant to output CRC）：0000</li>
        <!-- <li>Xor constant to output CRC: 0000</li> -->
        <li>该算法对于输入&quot;123456789&quot;的输出：31C3</li>
        <!-- <li>Output for &quot;123456789&quot;: 31C3</li> -->
        </ul>
        
        <p>CRC16的16位输出中的14位会被使用（这也是为什么上面的式子中有一个对 16384 取余的操作）。</p>
        <!-- <p>14 out of 16 bit of the output of CRC16 are used (this is why there is
        a modulo 16384 operation in the formula above).</p> -->
        
        <p>在我们的测试中，CRC16能相当好地把不同的键均匀地分配到 16384 个槽中。</p>
        <!-- <p>In our tests CRC16 behaved remarkably well in distributing different kind of
        keys evenly across the 16384 slots.</p> -->
        
        <p><strong>注意</strong>：在本文档的附录A中有CRC16算法的实现。</p>
        <!-- <p><strong>Note</strong>: A reference implementation of the CRC16 algorithm used is available in the Appendix A of this document.</p> -->

        <h2>键哈希标签（Keys hash tags）</h2>        
        <!-- <h2>Keys hash tags</h2> -->
        
        <p>计算哈希槽可以实现<strong>哈希标签（hash tags）</strong>，但这有一个例外。哈希标签是确保两个键都在同一个哈希槽里的一种方式。将来也许会使用到哈希标签，例如为了在集群<em>稳定</em>的情况下（没有在做碎片重组操作）允许某些多键操作。</p>
        <!-- <p>There is an exception for the computation of the hash slot that is used in order
        to implement <strong>hash tags</strong>. Hash tags are a way to ensure that two keys
        are allocated in the same hash slot. In the future this may be used, for example,
        in order to allow certain multi-keys operations while the cluster is <em>stable</em>
        (no resharding is in progress).</p> -->
        
        <p>为了实现哈希标签，哈希槽是用另一种不同的方式计算的。基本来说，如果一个键包含一个 &quot;{...}&quot; 这样的模式，只有 <code>{</code> 和 <code>}</code> 之间的字符串会被用来做哈希以获取哈希槽。但是由于可能出现多个 <code>{</code> 或 <code>}</code>，计算的算法如下：</p>
        <!-- <p>In order to implement hash tags, the hash slot is computed in a different
        way. Basically if the key contains a &quot;{...}&quot; pattern only the substring between
        <code>{</code> and <code>}</code> is hashed in order to obtain the hash slot. However since it is
        possible that there are multiple occurrences of <code>{</code> or <code>}</code> the algorithm is
        well specified by the following rules:</p> -->
        
        <ul>
        <li>如果键包含一个 <code>{</code> 字符。</li>
        <!-- <li>If the key contains a <code>{</code> character.</li> -->
        <li>那么在 <code>{</code> 的右边就会有一个 <code>}</code>。</li>
        <!-- <li>There is a <code>}</code> character on the right of <code>{</code></li> -->
        <li>在 <code>{</code> 和 <code>}</code> 之间会有一个或多个字符，第一个 <code>}</code> 一定是出现在第一个 <code>{</code> 之后。</li>
        <!-- <li>There are one or more characters between the first occurrence of <code>{</code> and the first occurrence of <code>}</code> after the first occurrence of <code>{</code>.</li> -->
        </ul>
        
        <p>然后不是直接计算键的哈希，只有在第一个 <code>{</code> 和它右边第一个 <code>}</code> 之间的内容会被用来计算哈希值。</p>
        <!-- <p>Then instead of hashing the key, only what is between the first occurrence of <code>{</code> and the first occurrence of <code>}</code> on its right are hashed.</p> -->
        
        <p>例子：</p>
        <!-- <p>Examples:</p> -->
        
        <ul>
        <li>比如这两个键 <code>{user1000}.following</code> 和 <code>{user1000}.followers</code> 会被哈希到同一个哈希槽里，因为只有 <code>user1000</code> 这个子串会被用来计算哈希值。</li>
        <!-- <li>The two keys <code>{user1000}.following</code> and <code>{user1000}.followers</code> will hash to the same hash slot since only the substring <code>user1000</code> will be hashed in order to compute the hash slot.</li> -->
        <li>对于 <code>foo{}{bar}</code> 这个键，整个键都会被用来计算哈希值，因为第一个出现的 <code>{</code> 和它右边第一个出现的 <code>}</code> 之间没有任何字符。</li>
        <!-- <li>For the key <code>foo{}{bar}</code> the whole key will be hashed as usually since the first occurrence of <code>{</code> is followed by <code>}</code> on the right without characters in the middle.</li> -->
        <li>对于 <code>foo{{bar}}zap</code> 这个键，用来计算哈希值的是 <code>{bar</code> 这个子串，因为它是第一个 <code>{</code> 及其右边第一个 <code>}</code> 之间的内容。</li>
        <!-- <li>For the key <code>foo{{bar}}zap</code> the substring <code>{bar</code> will be hashed, because it is the substring between the first occurrence of <code>{</code> and the first occurrence of <code>}</code> on its right.</li> -->
        <li>对于 <code>foo{bar}{zap}</code> 这个键，用来计算哈希值的是 <code>bar</code> 这个子串，因为算法会在第一次有效或无效（比如中间没有任何字节）地匹配到 <code>{</code> 和 <code>}</code> 的时候停止。</li>
        <!-- <li>For the key <code>foo{bar}{zap}</code> the substring <code>bar</code> will be hashed, since the algorithm stops at the first valid or invalid (without bytes inside) match of <code>{</code> and <code>}</code>.</li> -->
        <li>按照这个算法，如果一个键是以 <code>{}</code> 开头的话，那么就当作整个键会被用来计算哈希值。当使用二进制数据做为键名称的时候，这是非常有用的。</li>
        <!-- <li>What follows from the algorithm is that if the key starts with <code>{}</code>, it is guaranteed to be hashes as a whole. This is useful when using binary data as key names.</li> -->
        </ul>
        
        <p>下面是用 Ruby 和 C 语言实现的 <code>HASH_SLOT</code> 函数，有加上哈希标签例外。</p>
        <!-- <p>Adding the hash tags exception, the following is an implementation of the <code>HASH_SLOT</code> function in Ruby and C language.</p> -->
      
        <p>Ruby 样例代码：</p>  
        <!-- <p>Ruby example code:</p> -->
        
        <pre><code>def HASH_SLOT(key)&#x000A;    s = key.index &quot;{&quot;&#x000A;    if s&#x000A;        e = key.index &quot;}&quot;,s+1&#x000A;        if e &amp;&amp; e != s+1&#x000A;            key = key[s+1..e-1]&#x000A;        end&#x000A;    end&#x000A;    crc16(key) % 16384&#x000A;end&#x000A;</code></pre>
        
        <p>C 样例代码：</p>  
        <!-- <p>C example code:</p> -->
        
        <pre><code>unsigned int HASH_SLOT(char *key, int keylen) {&#x000A;    int s, e; /* start-end indexes of { and } */&#x000A;&#x000A;    /* Search the first occurrence of &#39;{&#39;. */&#x000A;    for (s = 0; s &lt; keylen; s++)&#x000A;        if (key[s] == &#39;{&#39;) break;&#x000A;&#x000A;    /* No &#39;{&#39; ? Hash the whole key. This is the base case. */&#x000A;    if (s == keylen) return crc16(key,keylen) &amp; 16383;&#x000A;&#x000A;    /* &#39;{&#39; found? Check if we have the corresponding &#39;}&#39;. */&#x000A;    for (e = s+1; e &lt; keylen; e++)&#x000A;        if (key[e] == &#39;}&#39;) break;&#x000A;&#x000A;    /* No &#39;}&#39; or nothing between {} ? Hash the whole key. */&#x000A;    if (e == keylen || e == s+1) return crc16(key,keylen) &amp; 16383;&#x000A;&#x000A;    /* If we are here there is both a { and a } on its right. Hash&#x000A;     * what is in the middle between { and }. */&#x000A;    return crc16(key+s+1,e-s-1) &amp; 16383;&#x000A;}&#x000A;</code></pre>
        
        <h2>集群节点属性</h2>
        <!-- <h2>Cluster nodes attributes</h2> -->
        
        <p>在集群中，每个节点都有一个唯一的名字。节点名字是一个十六进制表示的160 bit 随机数，这个随机数是节点第一次启动时获得的（通常是用 /dev/urandom）。
        节点会把它的ID保存在配置文件里，以后永远使用这个ID，只要这个节点配置文件没有被系统管理员删除掉。</p>
        <!-- <p>Every node has an unique name in the cluster. The node name is the
        hex representation of a 160 bit random number, obtained the first time a
        node is started (usually using /dev/urandom).
        The node will save its ID in the node configuration file, and will use the
        same ID forever, or at least as long as the node configuration file is not
        deleted by the system administrator.</p> -->

        <p>节点ID是用于在整个集群中标识每个节点。一个给定的节点可以在不改变节点ID的情况下改变 IP 和地址。集群能检测到 IP 或端口的变化，然后使用在集群连接（cluster bus）上的 gossip 协议来发布广播消息，通知配置变更。</p>
        <!-- <p>The node ID is used to identify every node across the whole cluster.
        It is possible for a given node to change IP and address without any need
        to also change the node ID. The cluster is also able to detect the change
        in IP/port and reconfigure broadcast the information using the gossip
        protocol running over the cluster bus.</p> -->
        
        <p>每个节点都有其他相关信息是所有节点都知道的：</p>
        <!-- <p>Every node has other associated information that all the other nodes
        know:</p> -->
        
        <ul>
        <li>节点的 IP 地址和 TCP 端口号。</li>
        <!-- <li>The IP address and TCP port where the node is located.</li> -->
        <li>各种标识。</li>
        <!-- <li>A set of flags.</li> -->
        <li>节点使用的哈希槽。</li>
        <!-- <li>A set of hash slots served by the node.</li> -->
        <li>最近一次用集群连接发送 ping 包的时间。</li>
        <!-- <li>Last time we sent a ping packet using the cluster bus.</li> -->
        <li>最近一次在回复中收到一个 pong 包的时间。</li>
        <!-- <li>Last time we received a pong packet in reply.</li> -->
        <li>最近一次标识节点失效的时间。</li>
        <!-- <li>The time at which we flagged the node as failing.</li> -->
        <li>该节点的从节点个数。</li>
        <!-- <li>The number of slaves of this node.</li> -->
        <li>如果该节点是从节点，会有主节点ID信息。（如果它是个主节点则该信息置为0000000...）</li>
        <!-- <li>The master node ID, if this node is a slave (or 0000000... if it is a master).</li> -->
        </ul>
        
        <p>使用 <code>CLUSTER NODES</code> 命令可以获得以上的一些信息，这个命令可以发送到集群中的所有节点，无论主节点还是从节点。</p>
        <!-- <p>Some of this information is available using the <code>CLUSTER NODES</code> command that
        can be sent to all the nodes in the cluster, both master and slave nodes.</p> -->
        
        <p>下面的例子是在一个只有三个节点的小集群中发送 <code>CLUSTER NODES</code> 命令到一个主节点得到的输出。</p>
        <!-- <p>The following is an example of output of <code>CLUSTER NODES</code> sent to a master
        node in a small cluster of three nodes.</p> -->
        
        <pre><code>$ redis-cli cluster nodes&#x000A;d1861060fe6a534d42d8a19aeb36600e18785e04 :0 myself - 0 1318428930 connected 0-1364&#x000A;3886e65cc906bfd9b1f7e7bde468726a052d1dae 127.0.0.1:6380 master - 1318428930 1318428931 connected 1365-2729&#x000A;d289c575dcbc4bdd2931585fd4339089e461a27d 127.0.0.1:6381 master - 1318428931 1318428931 connected 2730-4095&#x000A;</code></pre>
        
        <p>在上面罗列出来的信息中，各个域依次表示的是：节点ID，IP地址：端口号，标识，上一次发送 ping 包的时间，上一次收到 pong 包的时间，连接状态，节点使用的哈希槽。</p>
        <!-- <p>In the above listing the different fields are in order: node id, address:port, flags, last ping sent, last pong received, link state, slots.</p> -->
        
        <h2>集群拓扑结构</h2>
        <!-- <h2>Cluster topology</h2> -->
        
        <p>Redis 集群是一个网状结构，每个节点都通过 TCP 连接跟其他每个节点连接。</p>
        <!-- <p>Redis cluster is a full mesh where every node is connected with every other node using a TCP connection.</p> -->
        
        <p>在一个有 N 个节点的集群中，每个节点都有 N-1 个流出的 TCP 连接，和 N-1 个流入的连接。</p>
        <!-- <p>In a cluster of N nodes, every node has N-1 outgoing TCP connections, and N-1 incoming connections.</p> -->
        
        <p>这些 TCP 连接会永久保持，并不是按需创建的。</p>
        <!-- <p>These TCP connections are kept alive all the time and are not created on demand.</p> -->
        
        <h2>节点握手</h2>
        <!-- <h2>Nodes handshake</h2> -->
        
        <p>节点总是在集群连接端口接受连接，甚至会回复接收到的 ping 包，即使发送 ping 包的节点是不可信的。
        然而如果某个节点不被认为是在集群中，那么所有它发出的数据包都会被丢弃掉。</p>
        <!-- <p>Nodes always accept connection in the cluster bus port, and even reply to
        pings when received, even if the pinging node is not trusted.
        However all the other packets will be discarded by the node if the node
        is not considered part of the cluster.</p> -->
        
        <p>只有在两种方式下，一个节点才会认为另一个节点是集群中的一部分：</p>
        <!-- <p>A node will accept another node as part of the cluster only in two ways:</p> -->
        
        <ul>
        <li><p>当一个节点使用 <code>MEET</code> 消息介绍自己。一个 meet 消息跟一个 <a href="/commands/ping.html">PING</a> 消息完全一样，但它会强制让接收者接受发送者为集群中的一部分。 <strong>只有</strong>在系统管理员使用以下命令要求的时候，节点才会发送 <code>MEET</code> 消息给其他节点：</p>
        <!-- <li><p>If a node will present itself with a <code>MEET</code> message. A meet message is exactly
        like a <a href="/commands/ping.html">PING</a> message, but forces the receiver to accept the node as part of
        the cluster. Nodes will send <code>MEET</code> messages to other nodes <strong>only if</strong> the system administrator requests this via the following command:</p> -->
        
        <p>CLUSTER MEET ip port</p></li>
        <li><p>一个已被信任的节点能通过传播gossip消息让另一个节点被注册为集群中的一部分。也就是说，如果 A 知道 B，B 知道 C，那么 B 会向 A 发送 C 的gossip消息。A 收到后就会把 C 当作是网络中的一部分，并且尝试连接 C。</p></li>
        <!-- <li><p>A node will also register another node as part of the cluster if a node that is already trusted will gossip about this other node. So if A knows B, and B knows C, eventually B will send gossip messages to A about C. When this happens, A will register C as part of the network, and will try to connect with C.</p></li> -->
        </ul>
        
        <p>这意味着，只要我们往任何连接图中加入节点，它们最终会自动形成一个完全连接图。从根本上来说，这表示集群能自动发现其他节点，但前提是有一个由系统管理员强制创建的信任关系。</p>
        <!-- <p>This means that as long as we join nodes in any connected graph, they&#39;ll eventually form a fully connected graph automatically. This means that basically the cluster is able to auto-discover other nodes, but only if there is a trusted relationship that was forced by the system administrator.</p> -->
        
        <p>这个机制能防止不同的 Redis 集群因为 IP 地址变更或者其他网络事件而意外混合起来，从而使集群更具健壮性。</p>
        <!-- <p>This mechanism makes the cluster more robust but prevents that different Redis clusters will accidentally mix after change of IP addresses or other network related events.</p> -->
        
        <p>当节点的网络连接断掉时，它会积极尝试连接所有其他已知节点。</p>
        <!-- <p>All the nodes actively try to connect to all the other known nodes if the link is down.</p> -->
        
        <h2>MOVED 重定向</h2>
        <!-- <h2>MOVED Redirection</h2> -->
        
        <p>一个 Redis 客户端可以自由地向集群中的任意节点（包括从节点）发送查询。接收的节点会分析查询，如果这个命令是集群可以执行的（就是查询中只涉及一个键），那么节点会找这个键所属的哈希槽对应的节点。</p>
        <!-- <p>A Redis client is free to send queries to every node in the cluster, including
        slave nodes. The node will analyze the query, and if it is acceptable
        (that is, only a single key is mentioned in the query) it will see what
        node is responsible for the hash slot where the key belongs.</p> -->
        
        <p>如果刚好这个节点就是对应这个哈希槽，那么这个查询就直接被节点处理掉。否则这个节点会查看它内部的 哈希槽 -&gt; 节点ID 映射，然后给客户端返回一个 MOVED 错误。</p>
        <!-- <p>If the hash slot is served by the node, the query is simply processed, otherwise
        the node will check its internal hash slot -&gt; node ID map and will reply
        to the client with a MOVED error.</p> -->
        
        <p>一个 MOVED 错误如下：</p>
        <!-- <p>A MOVED error is like the following:</p> -->
        
        <pre><code>GET x&#x000A;-MOVED 3999 127.0.0.1:6381&#x000A;</code></pre>
        
        <p>这个错误包括键（3999）的哈希槽和能处理这个查询的节点的 ip：端口号（127.0.0.1:6381）。客户端需要重新发送查询到给定 ip 地址和端口号的节点。
        注意，即使客户端在重发查询之前等待了很长一段时间，与此同时集群的配置信息发生改变，如果哈希槽 3999 现在是为其他节点服务，那么目标节点会再向客户端回复一个 MOVED 错误。</p>
        <!-- <p>The error includes the hash slot of the key (3999) and the ip:port of the
        instance that can serve the query. The client need to reissue the query
        to the specified ip address and port. Note that even if the client waits
        a long time before reissuing the query, and in the meantime the cluster
        configuration changed, the destination node will reply again with a MOVED
        error if the hash slot 3999 is now served by another node.</p> -->
        
        <p>从集群的角度看，节点是以 ID 来标识的。我们尝试简化接口，所以只向客户端暴露哈希槽和用“ip:端口号”标识的 Redis 节点之间的映射。</p>
        <!-- <p>So while from the point of view of the cluster nodes are identified by
        IDs we try to simply our interface with the client just exposing a map
        between hash slots and Redis nodes identified by ip:port pairs.</p> -->
        
        <p>虽然并没有要求，但是客户端应该尝试记住哈希槽 3999 是服务于 127.0.0.1:6381。这样的话一旦有一个新的命令需要发送，它能计算出目标键的哈希槽，提高找到正确节点的机率。</p>
        <!-- <p>The client is not required to, but should try to memorize that hash slot
        3999 is served by 127.0.0.1:6381. This way once a new command needs to
        be issued it can compute the hash slot of the target key and pick the
        right node with higher chances.</p> -->
        
        <p>注意，当集群是稳定的时候，所有客户端最终都会得到一份哈希槽 -&gt; 节点的映射表，这样能使得集群效率非常高：客户端直接定位目标节点，不用重定向、或代理或发生其他单点故障（single point of failure entities）。</p>
        <!-- <p>Note that when the Cluster is stable, eventually all the clients will obtain
        a map of hash slots -&gt; nodes, making the cluster efficient, with clients
        directly addressing the right nodes without redirections nor proxies or
        other single point of failure entities.</p> -->
        
        <p>一个客户端也应该能处理本文后面将提到的 -ASK 重定向错误。</p>
        <!-- <p>A client should be also able to handle -ASK redirections that are described
        later in this document.</p> -->
        
        <h2>集群在线重配置（live reconfiguration）</h2>
        <!-- <h2>Cluster live reconfiguration</h2> -->
        
        <p>Redis 集群支持在集群运行过程中添加或移除节点。实际上，添加或移除节点都被抽象为同一个操作，那就是把哈希槽从一个节点移到另一个节点。</p>
        <!-- <p>Redis cluster supports the ability to add and remove nodes while the cluster
        is running. Actually adding or removing a node is abstracted into the same
        operation, that is, moving an hash slot from a node to another.</p> -->
        
        <ul>
        <li>向集群添加一个新节点，就是把一个空节点加入到集群中并把某些哈希槽从已存在的节点移到新节点上。</li>
        <!-- <li>To add a new node to the cluster an empty node is added to the cluster and some hash slot is moved from existing nodes to the new node.</li> -->
        <li>从集群中移除一个节点，就是把该节点上的哈希槽移到其他已存在的节点上。</li>
        <!-- <li>To remove a node from the cluster the hash slots assigned to that node are moved to other existing nodes.</li> -->
        </ul>
        
        <p>所以实现这个的核心是能把哈希槽移来移去。从实际角度看，哈希槽就只是一堆键，所以 Redis 集群在<em>重组碎片（reshard）</em>时做的就是把键从一个节点移到另一个节点。</p>
        <!-- <p>So the core of the implementation is the ability to move slots around.
        Actually from a practical point of view an hash slot is just a set of keys, so
        what Redis cluster really does during <em>resharding</em> is to move keys from
        an instance to another instance.</p> -->
        
        <p>为了理解这是怎么工作的，我们需要介绍 <code>CLUSTER</code> 的子命令，这些命令是用来操作 Redis 集群节点上的哈希槽转换表（slots translation table）。</p>
        <!-- <p>To understand how this works we need to show the <code>CLUSTER</code> subcommands
        that are used to manipulate the slots translation table in a Redis cluster node.</p> -->
        
        <p>以下是可用的子命令：</p>
        <!-- <p>The following subcommands are available:</p> -->
        
        <ul>
        <li>CLUSTER ADDSLOTS slot1 [slot2] ... [slotN]</li>
        <li>CLUSTER DELSLOTS slot1 [slot2] ... [slotN]</li>
        <li>CLUSTER SETSLOT slot NODE node</li>
        <li>CLUSTER SETSLOT slot MIGRATING node</li>
        <li>CLUSTER SETSLOT slot IMPORTING node</li>
        </ul>
        
        <p>头两个命令，<code>ADDSLOTS</code> 和 <code>DELSLOTS</code>，就是简单地用来给一个 Redis 节点指派（assign）或移除哈希槽。
        在哈希槽被指派后，节点会将这个消息通过 gossip 协议向整个集群传播。<code>ADDSLOTS</code> 命令通常是用于在一个集群刚建立的时候快速给所有节点指派哈希槽。</p>
        <!-- <p>The first two commands, <code>ADDSLOTS</code> and <code>DELSLOTS</code>, are simply used to assign
        (or remove) slots to a Redis node. After the hash slots are assigned they
        will propagate across all the cluster using the gossip protocol.
        The <code>ADDSLOTS</code> command is usually used when a new cluster is configured
        from scratch to assign slots to all the nodes in a fast way.</p> -->
        
        <p>当 <code>SETSLOT</code> 子命令使用 <code>NODE</code> 形式的时候，用来给指定 ID 的节点指派哈希槽。
        除此之外哈希槽能通过两个特殊的状态来设定，<code>MIGRATING</code> 和 <code>IMPORTING</code>：</p>
        <!-- <p>The <code>SETSLOT</code> subcommand is used to assign a slot to a specific node ID if
        the <code>NODE</code> form is used. Otherwise the slot can be set in the two special
        states <code>MIGRATING</code> and <code>IMPORTING</code>:</p> -->
        
        <ul>
        <li>当一个槽被设置为 MIGRATING，原来持有该哈希槽的节点仍会接受所有跟这个哈希槽有关的请求，但只有当查询的键还存在原节点时，原节点会处理该请求，否则这个查询会通过一个 <code>-ASK</code> 重定向（-ASK redirection）转发到迁移的目标节点。</li>
        <!-- <li>When a slot is set as MIGRATING, the node will accept all the requests
        for queries that are about this hash slot, but only if the key in question
        exists, otherwise the query is forwarded using a <code>-ASK</code> redirection to the
        node that is target of the migration.</li> -->
        <li>当一个槽被设置为 IMPORTING，只有在接受到 ASKING 命令之后节点才会接受所有查询这个哈希槽的请求。如果客户端一直没有发送 ASKING 命令，那么查询都会通过 <code>-MOVED</code> 重定向错误转发到真正处理这个哈希槽的节点那里。</li>
        <!-- <li>When a slot is set as IMPORTING, the node will accept all the requests
        for queries that are about this hash slot, but only if the request is
        preceded by an ASKING command. Otherwise if not ASKING command was given
        by the client, the query is redirected to the real hash slot owner via
        a <code>-MOVED</code> redirection error.</li> -->
        </ul>
        
        <p>这么讲可能显得有点奇怪，现在我们用实例让它更清晰些。假设我们有两个 Redis 节点，称为 A 和 B。我们想要把哈希槽 8 从 节点A 移到 节点B，所以我们发送了这样的命令：</p>
        <!-- <p>At first this may appear strange, but now we&#39;ll make it more clear.
        Assume that we have two Redis nodes, called A and B.
        We want to move hash slot 8 from A to B, so we issue commands like this:</p> -->
        
        <ul>
        <li>我们向 节点B 发送：CLUSTER SETSLOT 8 IMPORTING A</li>
        <!-- <li>We send B: CLUSTER SETSLOT 8 IMPORTING A</li> -->
        <li>我们向 节点A 发送：CLUSTER SETSLOT 8 MIGRATING B</li>
        <!-- <li>We send A: CLUSTER SETSLOT 8 MIGRATING B</li> -->
        </ul>
        
        <p>其他所有节点在每次被询问到的一个键是属于哈希槽 8 的时候，都会把客户端引向节点&quot;A&quot;。具体如下：</p>
        <!-- <p>All the other nodes will continue to point clients to node &quot;A&quot; every time
        they are queried with a key that belongs to hash slot 8, so what happens
        is that:</p> -->
        
        <ul>
        <li>所有关于已存在的键的查询都由节点&quot;A&quot;处理。</li>
        <!-- <li>All the queries about already existing keys are processed by &quot;A&quot;.</li> -->
        <li>所有关于不存在于节点 A 的键都由节点&quot;B&quot;处理。</li>
        <!-- <li>All the queries about non existing keys in A are processed by &quot;B&quot;.</li> -->
        </ul>
        
        <p>这种方式让我们可以不用在节点 A 中创建新的键。同时，一个叫做 <code>redis-trib</code> 的特殊客户端，它也是 Redis 集群的配置程序（configuration utility），会确保把已存在的键从节点 A 移到节点 B。这通过以下命令实现：</p>
        <!-- <p>This way we no longer create new keys in &quot;A&quot;.
        In the meantime, a special client that is called <code>redis-trib</code> and is
        the Redis cluster configuration utility will make sure to migrate existing
        keys from A to B. This is performed using the following command:</p> -->
        
        <pre><code>CLUSTER GETKEYSINSLOT slot count&#x000A;</code></pre>
        
        <p>上面这个命令会返回指定的哈希槽中 <code>count</code> 个键。对于每个返回的键，redis-trib 向节点 A 发送一个 <a href="/commands/migrate.html">MIGRATE</a> 命令，这样会以原子性的方式（在移动键的过程中两个节点都被锁住，以免出现竞争状况）把指定的键从节点 A 移到节点 B。以下是 <a href="/commands/migrate.html">MIGRATE</a> 的工作原理：</p>
        <!-- <p>The above command will return <code>count</code> keys in the specified hash slot.
        For every key returned, redis-trib sends node A a <a href="/commands/migrate.html">MIGRATE</a> command, that
        will migrate the specified key from A to B in an atomic way (both instances
        are locked for the time needed to migrate a key so there are no race
        conditions). This is how <a href="/commands/migrate.html">MIGRATE</a> works:</p> -->
        
        <pre><code>MIGRATE target_host target_port key target_database id timeout&#x000A;</code></pre>
        
        <p>执行 <a href="/commands/migrate.html">MIGRATE</a> 命令的节点会连接到目标节点，把序列化后的 key 发送过去，一旦收到 OK 回复就会从它自己的数据集中删除老的 key。所以从一个外部客户端看来，在某个时间点，一个 key 要不就存在于节点 A 中要不就存在于节点 B 中。</p>
        <!-- <p><a href="/commands/migrate.html">MIGRATE</a> will connect to the target instance, send a serialized version of
        the key, and once an OK code is received will delete the old key from its own
        dataset. So from the point of view of an external client a key either exists
        in A or B in a given time.</p> -->
        
        <p>在 Redis 集群中，不需要指定一个除了 0 号之外的数据库，但 <a href="/commands/migrate.html">MIGRATE</a> 命令能用于其他跟 Redis 集群无关的的任务，所以它是一个足够通用的命令。<a href="/commands/migrate.html">MIGRATE</a> 命令被优化了，使得即使在移动像长列表这样的复杂键仍然能做到快速。
        不过当在重配置一个拥有很多键且键的数据量都很大的集群的时候，这个过程就并不那么好了，对于使用数据库的应用程序来说就会有延时这个限制。</p>
        <!-- <p>In Redis cluster there is no need to specify a database other than 0, but
        <a href="/commands/migrate.html">MIGRATE</a> can be used for other tasks as well not involving Redis cluster so
        it is a general enough command.
        <a href="/commands/migrate.html">MIGRATE</a> is optimized to be as fast as possible even when moving complex
        keys such as long lists, but of course in Redis cluster reconfiguring the
        cluster where big keys are present is not considered a wise procedure if
        there are latency constraints in the application using the database.</p> -->
        
        <h2>ASK 重定向</h2>
        <!-- <h2>ASK redirection</h2> -->
        
        <p>在前面的章节中，我们简短地提到了 ASK 重定向（ASK redirection），为什么我们不能单纯地使用 MOVED 重定向呢？因为当我们使用 MOVED 的时候，意味着我们认为哈希槽永久地被另一个不同的节点处理，并且希望接下来的所有查询都尝试发到这个指定的节点上去。而 ASK 意味着我们只要下一个查询发送到指定节点上去。</p>
        <!-- <p>In the previous section we briefly talked about ASK redirection, why we
        can&#39;t simply use the MOVED redirection? Because while MOVED means that
        we think the hash slot is permanently served by a different node and the
        next queries should be tried against the specified node, ASK means to
        only ask the next query to the specified node.</p> -->
        
        <p>这个命令是必要的，因为下一个关于哈希槽 8 的查询需要的键或许还在节点 A 中，所以我们希望客户端尝试在节点 A 中查找，如果需要的话也在节点 B 中查找。
        由于这是发生在 16384 个槽的其中一个槽，所以对于集群的性能影响是在可接受的范围。</p>
        <!-- <p>This is needed because the next query about hash slot 8 can be about the
        key that is still in A, so we always want that the client will try A and
        then B if needed. Since this happens only for one hash slot out of 16384
        available the performance hit on the cluster is acceptable.</p> -->
        
        <p>然而我们需要强制客户端的行为，以确保客户端会在尝试 A 中查找后去尝试在 B 中查找。如果客户端在发送查询前发送了 ASKING 命令，那么节点 B 只会接受被设为 IMPORTING 的槽的查询。</p>
        <!-- <p>However we need to force that client behavior, so in order to make sure
        that clients will only try slot B after A was tried, node B will only
        accept queries of a slot that is set as IMPORTING if the client send the
        ASKING command before sending the query.</p> -->
        
        <p>本质上来说，ASKING 命令在客户端设置了一个一次性标识（one-time flag），强制一个节点可以执行一次关于带有 IMPORTING 状态的槽的查询。</p>
        <!-- <p>Basically the ASKING command set a one-time flag on the client that forces
        a node to serve a query about an IMPORTING slot.</p> -->
        
        <p>所以从客户端看来，ASK 重定向的完整语义如下：</p>
        <!-- <p>So the full semantics of the ASK redirection is the following, from the
        point of view of the client.</p> -->
        
        <ul>
        <li>如果接受到 ASK 重定向，那么把查询的对象调整为指定的节点。</li>
        <!-- <li>If ASK redirection is received send only the query in object to the specified node.</li> -->
        <li>先发送 ASKING 命令，再开始发送查询。</li>
        <!-- <li>Start the query with the ASKING command.</li> -->
        <li>现在不要更新本地客户端的映射表把哈希槽 8 映射到节点 B。</li>
        <!-- <li>Don&#39;t update local client tables to map hash slot 8 to B for now.</li> -->
        </ul>
        
        <p>一旦完成了哈希槽 8 的转移，节点 A 会发送一个 MOVED 消息，客户端也许会永久地把哈希槽 8 映射到新的 ip:端口号 上。
        注意，即使客户端出现bug，过早地执行这个映射更新，也是没有问题的，因为它不会在查询前发送 ASKING 命令，节点 B 会用 MOVED 重定向错误把客户端重定向到节点 A 上。</p>
        <!-- <p>Once the hash slot 8 migration is completed, A will send a MOVED message and
        the client may permanently map hash slot 8 to the new ip:port pair.
        Note that however if a buggy client will perform the map earlier this is not
        a problem since it will not send the ASKING command before the query and B
        will redirect the client to A using a MOVED redirection error.</p> -->
        
        <h1>容错性（Fault Tolerance）</h1>
        <!-- <h1>Fault Tolerance</h1> -->
        
        <h2>节点心跳（heartbeat）和 gossip 消息</h2>
        <!-- <h2>Nodes heartbeat and gossip messages</h2> -->
        
        <p>集群里的节点交换 ping / pong 数据包。</p>
        <!-- <p>Nodes in the cluster exchange ping / pong packets.</p> -->
        
        <p>通常一个节点每秒会随机 ping 几个节点，这样发送的 ping 包（和接收到的 pong 包）的总数会是一个跟集群节点数量无关的常数。</p>
        <!-- <p>Usually a node will ping a few random nodes every second so that the total number of ping packets send (and pong packets received) is a constant amount regardless of the number of nodes in the cluster.</p> -->
        
        <p>不过每个节点都会保证去 ping 满足这个条件的其他节点：在过去的一半 <code>NODE_TIMEOUT</code> 时间里都没有发送 ping 包过去或接收从那节点发来的 pong 包的节点。
        在 <code>NODE_TIMEOUT</code> 这么长的时间过去之前，若当前的 TCP 连接有问题，节点会尝试去重连接，以确保不会被当作不可达的节点。</p>
        <!-- <p>However every node makes sure to ping every other node that we don&#39;t either sent a ping or received a pong for longer than half the <code>NODE_TIMEOUT</code> time. Before <code>NODE_TIMEOUT</code> has elapsed, nodes also try to reconnect the TCP link with another node to make sure nodes are not believed to be unreachable only because there is a problem in the current TCP connection.</p> -->
        
        <p>如果 <code>NODE_TIMEOUT</code> 被设为一个很小的数而节点数量（N）非常大，那么消息交流数量会比 <span class="math">O(N) </span> 更大，因为每个节点都会尝试去 ping 每一个在过去一半 <code>NODE_TIMEOUT</code> 时间里都没更新信息的节点。</p>
        <!-- <p>The amount of messages exchanged can be bigger than <span class="math">O(N) </span>if <code>NODE_TIMEOUT</code> is set to a small figure and the number of nodes (N) is very large, since every node will try to ping every other node for which we don&#39;t have fresh information for half the <code>NODE_TIMEOUT</code> time.</p> -->
        
        <p>例如在一个拥有 100 个节点的集群里，节点超时时限设为 60 秒，每个节点在每 30 秒中会尝试发送 99 个 ping 包，也就是每秒发送的 ping 包数量是 3.3 个，乘以 100 个节点就是整个集群每秒有 330 个 ping 包。</p>
        <!-- <p>For example in a 100 nodes cluster with a node timeout set to 60 seconds, every node will try to send 99 pings every 30 seconds, with a total amount of pings of 3.3 per second, that multiplied for 100 nodes is 330 pings per second in the total cluster.</p> -->
        
        <p>利用 Redis 集群中已经交流过的 gossip 信息可以显著地减少消息交流数量。比如我们也可以在一半 <code>NODE_TIMEOUT</code> 时间里只 ping 那些被其他节点报告过已处于&quot;可能失效&quot;状态（详见下文）的节点，而那些被报告仍处于工作状态的节点就只是尽力在每秒有限的几个包里 ping 一下。然而在真实环境中测试的时候，设置了小的 <code>NODE_TIMEOUT</code> 常数的大集群都挺可靠地工作着，所以将来会在测试实际部署大集群的时候考虑这个变更。</p>
        <!-- <p>There are ways to use the gossip information already exchanged by Redis Cluster to reduce the amount of messages exchanged in a significant way. For example we may ping within half <code>NODE_TIMEOUT</code> only nodes that are already reported to be in &quot;possible failure&quot; state (see later) by other nodes, and ping the other nodes that are reported as working only in a best-effort way within the limit of the few packets per second. However in real-world tests large clusters with very small <code>NODE_TIMEOUT</code> settings used to work reliably so this change will be considered in the future as actual deployments of large clusters will be tested.</p> -->
        
        <h2>Ping 和 Pong 数据包内容</h2>
        <!-- <h2>Ping and Pong packets content</h2> -->
        
        <p>Ping 和 Pong 数据包都包含着一个头部（header），这在这类数据包（比如请求投票的数据包）中是很常见的。一个特殊的 Gossip 字段（Gossip Section）就是 Ping 包和 Pong 包里一个特殊部分。</p>
        <!-- <p>Ping and Pong packets contain an header that is common to all the kind of packets (for instance packets to request a vote), and a special Gossip Section that is specific of Ping and Pong packets.</p> -->
        
        <p>头部会包含以下这些信息：</p>
        <!-- <p>The common header has the following information:</p> -->
        
        <ul>
        <li>节点 ID，在节点第一次创建的时候赋值的一个 160 bit 的伪随机字符串，在作为 Redis 集群节点的一生中都保持不变。</li>
        <!-- <li>Node ID, that is a 160 bit pseudorandom string that is assigned the first time a node is created and remains the same for all the life of a Redis Cluster node.</li> -->
        <li><code>currentEpoch</code> 和 <code>configEpoch</code> 两个域，用来挂载 Redis 集群使用的分布式算法（这会在下一节中详细解释）。如果节点是一个从节点，？？？</li>
        <li>The <code>currentEpoch</code> and <code>configEpoch</code> field, that are used in order to mount the distributed algorithms used by Redis Cluster (this is explained in details in the next sections). If the node is a slave the <code>configEpoch</code> is the last known <code>configEpoch</code> of the master.</li>
        <li>节点标识，标识一个节点是从节点还是主节点，还有其他只占用一个 bit 的节点信息。</li>
        <!-- <li>The node flags, indicating if the node is a slave, a master, and other single-bit node information.</li> -->
        <li>给定节点负责的哈希槽的位图（bitmap），如果该节点是从节点的话，就是一个其主节点负责的哈希槽位图。</li>
        <!-- <li>A bitmap of the hash slots served by a given node, or if the node is a slave, a bitmap of the slots served by its master.</li> -->
        <li>端口号：发送者的 TCP 基本端口号（也就是，这个端口号是 Redis 用来接收客户端命令的，给这个值加上 10000 就能获得集群端口号）。</li>
        <!-- <li>Port: the sender TCP base port (that is, the port used by Redis to accept client commands, add 10000 to this to obtain the cluster port).</li> -->
        <li>状态：从发送者的角度看来的集群状态（停机还是ok）。</li>
        <!-- <li>State: the state of the cluster from the point of view of the sender (down or ok).</li> -->
        <li>如果这是个从节点，那么会有主节点 ID。</li>
        <!-- <li>The master node ID, if this is a slave.</li> -->
        </ul>
        
        <p>ping 包和 pong 包都包含着一个 gossip 字段。这个字段是用来让接收者知道发送者是怎么看待集群中的其他节点。gossip 字段只包含在发送者已知节点集合里随机取的一些节点的信息。</p>
        <!-- <p>Ping and pong packets contain a gossip section. This section offers to the receiver a view about what the sender node thinks about other nodes in the cluster. The gossip section only contains information about a few random nodes among the known nodes set of the sender.</p> -->

        <p>在 gossip 字段里报告的是节点的以下几个域：</p>        
        <!-- <p>For every node added in the gossip section the following fields are reported:</p> -->
        
        <ul>
        <li>节点 ID。</li>
        <!-- <li>Node ID.</li> -->
        <li>节点的 IP 和端口号。</li>
        <!-- <li>IP and port of the node.</li> -->
        <li>节点标识。</li>
        <!-- <li>Node flags.</li> -->
        </ul>
        
        <p>从发送者的角度看来，gossip 字段是让接收的节点能获得其他节点的状态信息。这对于失效检测或者发现集群中的其他节点都是非常有用的。</p>
        <!-- <p>Gossip sections allow receiving nodes to get information about the state of other nodes from the point of view of the sender. This is useful both for failure detection and to discover other nodes in the cluster.</p> -->
        
        <h2>失效检测（Failure detection）</h2>
        <!-- <h2>Failure detection</h2> -->
        
        <p>Redis 集群失效检测是用来识别出大多数节点何时无法访问某一个主节点或从节点。当这个事件发生时，就提升一个从节点来做主节点；若如果无法提升从节点来做主节点的话，那么整个集群就置为错误状态并停止接收客户端的查询。</p>
        <!-- <p>Redis Cluster failure detection is used to recognize when a master or slave node is no longer reachable by the majority of nodes, and as a result of this event, either promote a slave to the role of master, of when this is not possible, put the cluster in an error state to stop receiving queries from clients.</p> -->
        
        <p>每个节点都有一份跟其他已知节点相关的标识列表。其中有两个标识是用于失效检测，分别是 <code>PFAIL</code> 和 <code>FAIL</code>。<code>PFAIL</code> 表示<em>可能失效（Possible failure）</em>，这是一个非公认的（non acknowledged）失效类型。<code>FAIL</code> 表示一个节点已经失效，而且这个情况已经被大多数主节点在某段固定时间内确认过的了。</p>
        <!-- <p>Every node takes a list of flags associated with other known nodes. There are two flags that are used for failure detection that are called <code>PFAIL</code> and <code>FAIL</code>. <code>PFAIL</code> means <em>Possible failure</em>, and is a non acknowledged failure type. <code>FAIL</code> means that a node is failing and that this condition was confirmed by a majority of masters in a fixed amount of time.</p> -->
        
        <p><strong>PFAIL 标识:</strong></p>
        <!-- <p><strong>PFAIL flag:</strong></p> -->
        
        <p>当一个节点在超过 <code>NODE_TIMEOUT</code> 时间后仍无法访问某个节点，那么它会用 <code>PFAIL</code> 来标识这个不可达的节点。无论节点类型是什么，主节点和从节点都能标识其他的节点为 <code>PFAIL</code>。</p>
        <!-- <p>A node flags another node with the <code>PFAIL</code> flag when the node is not reachable for more than <code>NODE_TIMEOUT</code> time. Both master and slave nodes can flag another node as <code>PFAIL</code>, regardless of its type.</p> -->
        
        <p>Redis 集群节点的不可达性（non reachability）是指，发送给某个节点的一个<strong>活跃的 ping 包（active ping）</strong>(一个我们发送后要等待其回复的 ping 包)已经等待了超过 <code>NODE_TIMEOUT</code> 时间，那么我们认为这个节点具有不可达性。为了让这个机制能正常工作，<code>NODE_TIMEOUT</code> 必须比网络往返时间（network round trip time）大。节点为了在普通操作中增加可达性，当在经过一半 <code>NODE_TIMEOUT</code> 时间还没收到目标节点对于 ping 包的回复的时候，就会马上尝试重连接该节点。这个机制能保证连接都保持有效，所以节点间的失效连接通常都不会导致错误的失效报告。</p>
        <!-- <p>The concept of non reachability for a Redis Cluster node is that we have an <strong>active ping</strong> (a ping that we sent for which we still have to get a reply) pending for more than <code>NODE_TIMEOUT</code>, so for this mechanism to work the <code>NODE_TIMEOUT</code> must be large compared to the network round trip time. In order to add reliability during normal operations, nodes will try to reconnect with other nodes in the cluster as soon as half of the <code>NODE_TIMEOUT</code> has elapsed without a reply to a ping. This mechanism ensures that connections are kept alive so broken connections should usually not result into false failure reports between nodes.</p> -->
        
        <p><strong>FAIL 标识:</strong></p>
        <!-- <p><strong>FAIL flag:</strong></p> -->
        
        <p>单独一个 <code>PFAIL</code> 标识只是每个节点的一些关于其他节点的本地信息，它不是为了起作用而使用的，也不足够触发从节点的提升。要让一个节点真正被认为失效了，那需要让 <code>PFAIL</code> 状态上升为 <code>FAIL</code> 状态。</p>
        <!-- <p>The <code>PFAIL</code> flag alone is just some local information every node has about other nodes, but it is not used in order to act and is not sufficient to trigger a slave promotion. For a node to be really considered down the <code>PFAIL</code> condition needs to be promoted to a <code>FAIL</code> condition.</p> -->
        
        <p>在本文的节点心跳章节有提到的，每个节点向其他每个节点发送的 gossip 消息中有包含一些随机的已知节点的状态。最终每个节点都能收到一份其他每个节点的节点标识。使用这种方法，每个节点都有一套机制去标记他们检查到的关于其他节点的失效状态。</p>
        <!-- <p>As outlined in the node heartbeats section of this document, every node sends gossip messages to every other node including the state of a few random known nodes. So every node eventually receives the set of node flags for every other node. This way every node has a mechanism to signal other nodes about failure conditions they detected.</p> -->
        
        <p>当下面的条件满足的时候，会使用这个机制来让 <code>PFAIL</code> 状态升级为 <code>FAIL</code> 状态：</p>
        <!-- <p>This mechanism is used in order to escalate a <code>PFAIL</code> condition to a <code>FAIL</code> condition, when the following set of conditions are met:</p> -->
        
        <ul>
        <li>某个节点，我们称为节点 A，标记另一个节点 B 为 <code>PFAIL</code>。</li>
        <!-- <li>Some node, that we&#39;ll call A, has another node B flagged as <code>PFAIL</code>.</li> -->
        <li>节点 A 通过 gossip 字段收集到集群中大部分主节点标识的节点 B 的状态信息。</li>
        <!-- <li>Node A collected, via gossip sections, information about the state of B from the point of view of the majority of masters in the cluster.</li> -->
        <li>大部分主节点标记节点 B 为 <code>PFAIL</code> 状态，或者在 <code>NODE_TIMEOUT * FAIL_REPORT_VALIDITY_MULT</code> 这个时间内是处于 <code>PFAIL</code> 状态。</li>
        <!-- <li>The majority of masters signaled the <code>PFAIL</code> or <code>PFAIL</code> condition within <code>NODE_TIMEOUT * FAIL_REPORT_VALIDITY_MULT</code> time.</li> -->
        </ul>
        
        <p>如果以上所有条件都满足了，那么节点 A 会：</p>
        <!-- <p>If all the above conditions are true, Node A will:</p> -->
        
        <ul>
        <li>标记节点 B 为 <code>FAIL</code>。</li>
        <!-- <li>Mark the node as <code>FAIL</code>.</li> -->
        <li>向所有可达节点发送一个 <code>FAIL</code> 消息。</li>
        <!-- <li>Send a <code>FAIL</code> message to all the reachable nodes.</li> -->
        </ul>
        
        <p><code>FAIL</code> 消息会强制每个接收到这消息的节点把节点 B 标记为 <code>FAIL</code> 状态。</p>
        <!-- <p>The <code>FAIL</code> message will force every receiving node to mark the node in <code>FAIL</code> state.</p> -->
        
        <p>注意，<em>FAIL 标识基本都是单向的</em>，也就是说，一个节点能从 <code>PFAIL</code> 状态升级到 <code>FAIL</code> 状态，但要清除 <code>FAIL</code> 标识只有以下两种可能方法：</p>
        <!-- <p>Note that <em>the FAIL flag is mostly one way</em>, that is, a node can go from <code>PFAIL</code> to <code>FAIL</code>, but for the <code>FAIL</code> flag to be cleared there are only two possibilities:</p> -->
        
        <ul>
        <li>节点已经恢复可达的，并且它是一个从节点。在这种情况下，<code>FAIL</code> 标识可以清除掉，因为从节点并没有被故障转移。</li>
        <!-- <li>The node is already reachable, and it is a slave. In this case the <code>FAIL</code> flag can be cleared as slaves are not failed over.</li> -->
        <li>节点已经恢复可达的，而且它是一个主节点，但经过了很长时间（N * <code>NODE_TIMEOUT</code>）后也没有检测到任何从节点被提升了。</li>
        <!-- <li>The node is already reachable, is a master, but a long time (N times the <code>NODE_TIMEOUT</code>) has elapsed without any detectable slave promotion.</li> -->
        </ul>
        
        <p><strong><code>PFAIL</code> -&gt; <code>FAIL</code> 的转变使用一种弱协议（agreement）：</strong></p>
        <!-- <p><strong>While the <code>PFAIL</code> -&gt; <code>FAIL</code> transition uses a form of agreement, the agreement used is weak:</strong></p> -->
        
        <p>1) 节点是在一段时间内收集其他节点的信息，所以即使大多数主节点要去&quot;同意&quot;标记某节点为 FAIL，实际上这只是表明说我们在不同时间里从不同节点收集了信息，得出当前的状态不一定是稳定的结论。</p>
        <!-- <p>1) Nodes collect views of other nodes during some time, so even if the majority of master nodes need to &quot;agree&quot;, actually this is just state that we collected from different nodes at different times and we are not sure this state is stable.</p> -->
        
        <p>2) 当每个节点检测到 <code>FAIL</code> 节点的时候会强迫集群里的其他节点把各自对该节点的记录更新为 <code>FAIL</code>，但没有一种方式能保证这个消息能到达所有节点。比如有个节点可能检测到了 <code>FAIL</code> 的节点，但是因为分区，这个节点无法到达其他任何一个节点。</p>
        <!-- <p>2) While every node detecting the <code>FAIL</code> condition will force that condition on other nodes in the cluster using the <code>FAIL</code> message, there is no way to ensure the message will reach all the nodes. For instance a node may detect the <code>FAIL</code> condition and because of a partition will not be able to reach any other node.</p> -->
        
        <p>然而 Redis 集群的失效检测有一个要求：最终所有节点都应该同意给定节点的状态是 <code>FAIL</code>，哪怕它处于分区。有两种情况是来源于脑裂情况（？），或者是小部分节点相信该节点处于 <code>FAIL</code> 状态，或者是相信节点不处于 <code>FAIL</code> 状态。在这两种情况中，最后集群都会认为给定的节点只有一个状态：</p>
        <!-- <p>However the Redis Cluster failure detection has a requirement: eventually all the nodes should agree about the state of a given node even in case of partitions. There are two cases that can originate from split brain conditions, either some minority of nodes believe the node is in <code>FAIL</code> state, or a minority of nodes believe the node is not in <code>FAIL</code> state. In both the cases eventually the cluster will have a single view of the state of a given node:</p> -->
        
        <p><strong>第 1 种情况</strong>: 如果大多数节点都标记了某个节点为 <code>FAIL</code>，由于链条反应，这个主节点最终会被标记为 <code>FAIL</code>。</p>
        <!--<p><strong>Case 1</strong>: If an actual majority of masters flagged a node as <code>FAIL</code>, for the chain effect every other node will flag the master as <code>FAIL</code> eventually.</p> -->
        
        <p><strong>第 2 种情况</strong>: 当只有小部分的主节点标记某个节点为 <code>FAIL</code> 的时候，从节点的提升并不会发生（它是使用一个更正式的算法来保证每个节点最终都会知道节点的提升。），并且每个节点都会根据上面的清除规则（在经过了一段时间 &gt; N  * <code>NODE_TIMEOUT</code> 后仍没有从节点提升操作）来清除 <code>FAIL</code> 状态。</p>
        <!-- <p><strong>Case 2</strong>: When only a minority of masters flagged a node as <code>FAIL</code>, the slave promotion will not happen (as it uses a more formal algorithm that makes sure everybody will know about the promotion eventually) and every node will clear the <code>FAIL</code> state for the <code>FAIL</code> state clearing rules above (no promotion after some time &gt; of N times the <code>NODE_TIMEOUT</code>).</p> -->
        
        <p><strong>本质上来说，<code>FAIL</code> 标识只是用来触发从节点提升（slave promotion）算法的安全部分。</strong>理论上一个从节点会在它的主节点不可达的时候独立起作用并且启动从节点提升程序，然后等待主节点来拒绝认可该提升（如果主节点对大部分节点恢复连接）。<code>PFAIL -&gt; FAIL</code> 的状态变化、弱协议、强制在集群的可达部分用最短的时间传播状态变更的 <code>FAIL</code> 消息，这些东西增加的复杂性有实际的好处。由于这种机制，如果集群处于错误状态的时候，所有节点都会在同一时间停止接收写入操作，这从使用 Redis 集群的应用的角度来看是个很好的特性。还有非必要的选举，是从节点在无法访问主节点的时候发起的，若该主节点能被其他大多数主节点访问的话，这个选举会被拒绝掉。</p>
        <!-- <p><strong>Basically the <code>FAIL</code> flag is only used as a trigger to run the safe part of the algorithm</strong>  for the slave promotion. In theory a slave may act independently and start a slave promotion when its master is not reachable, and wait for the masters to refuse the provide acknowledgment if the master is actually reachable by the majority. However the added complexity of the <code>PFAIL -&gt; FAIL</code> state, the weak agreement, and the <code>FAIL</code> message to force the propagation of the state in the shortest amount of time in the reachable part of the cluster, have practical advantages. Because of this mechanisms usually all the nodes will stop accepting writes about at the same time if the cluster is in an error condition, that is a desirable feature from the point of view of applications using Redis Cluster. Also not necessary elections, initiated by slaves that can&#39;t reach its master that is otherwise reachable by the majority of the other master nodes, are avoided.</p> -->
        
        <h2>集群阶段（Cluster epoch）</h2>
        <!-- <h2>Cluster epoch</h2> -->
        
        <p>Redis 集群使用一个类似于木筏算法（Raft algorithm）&quot;术语&quot;的概念。在 Redis 集群中这个术语叫做 阶段（epoch），它是用来记录事件的版本号，所以当有多个节点提供了冲突的信息的时候，另外的节点就可以通过这个状态来了解哪个是最新的。</p>
        <!-- <p>Redis Cluster uses a concept similar to the Raft algorithm &quot;term&quot;. In Redis Cluster the term is called epoch instead, and it is used in order to give an incremental version to events, so that when multiple nodes provide conflicting information, it is possible for another node to understand which state is the most up to date.</p> -->
        
        <p><code>currentEpoch</code> 是一个 64bit 的 unsigned 数。</p>
        <!-- <p>The <code>currentEpoch</code> is a 64 bit unsigned number.</p> -->
        
        <p>Redis 集群中的每个节点，包括主节点和从节点，都在创建的时候设置了 <code>currentEpoch</code> 为0。</p>
        <!-- <p>At node creation every Redis Cluster node, both slaves and master nodes, set the <code>currentEpoch</code> to 0.</p> -->
        
        <p>当节点接收到来自其他节点的 ping 包或 pong 包的时候，如果发送者的 epoch（集群连接消息头部的一部分）大于该节点的 epoch，那么更新发送者的 epoch 为 <code>currentEpoch</code>。</p>
        <!-- <p>Every time a ping or pong is received from another node, if the epoch of the sender (part of the cluster bus messages header) is greater than the local node epoch, then <code>currentEpoch</code> is updated to the sender epoch.</p> -->
        
        <p>由于这个语义，最终所有节点都会支持集群中较大的 epoch。</p>
        <!-- <p>Because of this semantics eventually all the nodes will agree to the greater epoch in the cluster.</p> -->
        
        <p>这个信息在此处是用于，当一个节点的状态发生改变的时候为了执行一些动作寻求其他节点的同意（agreement）。</p>
        <!-- <p>The way this information is used is when the state is changed and a node seeks agreement in order to perform some action.</p> -->
        
        <p>目前这个只发生在从节点的提升过程，这个将在下一节中详述。本质上说，epoch 是一个集群里的逻辑时钟，并决定一个给定的消息赢了另一个带着更小 epoch 的消息。</p>
        <!-- <p>Currently this happens only during slave promotion, as described in the next section. Basically the epoch is a logical clock for the cluster and dictates whatever a given information wins over one with a smaller epoch.</p> -->
        
        <h2>配置阶段（Config epoch）</h2>
        <!-- <h2>Config epoch</h2> -->
        
        <p>每一个主节点总是通过发送 ping 包和 pong 包向别人宣传它的 <code>configEpoch</code> 和一份表示它负责的哈希槽的位图。</p>
        <!-- <p>Every master always advertises its <code>configEpoch</code> in ping and pong packets along with a bitmap advertising the set of slots it serves.</p> -->
        
        <p>当一个新节点被创建的时候，主节点中的 <code>configEpoch</code> 设为零。</p>
        <!-- <p>The <code>configEpoch</code> is set to zero in masters when a new node is created.</p> -->
        
        <p>从节点由于故障转移事件被提升为主节点时，为了取代它那失效的主节点，会把 <code>configEpoch</code> 设置为它赢得选举的时候的 <code>configEpoch</code> 值。</p>
        <!-- <p>Slaves that are promoted to master because of a failover event instead have a <code>configEpoch</code> that is set to the value of the <code>currentEpoch</code> at the time the slave won the election in order to replace its failing master.</p> -->
        
        <p><code>configEpoch</code> 用于在不同节点提出不同的配置信息的时候（这种情况或许会在分区之后发生）解决冲突，这将在下一节解释。</p>
        <!-- <p>As explained in the next sections the <code>configEpoch</code> helps to resolve conflicts due to different nodes claiming diverging configurations (a condition that may happen after partitions).</p> -->
        
        <p>从节点也会在 ping 包和 pong 包中向别人宣传它的 <code>configEpoch</code> 域，不过从节点的这个域表示的是上一次跟它的主节点交换数据的时候主节点的 <code>configEpoch</code> 值。这能让其他个体检测出从节点的配置信息是不是需要更新了（主节点不会给一个配置信息过时的从节点投票）。</p>
        <!-- <p>Slave nodes also advertise the <code>configEpoch</code> field in ping and pong packets, but in case of slaves the field represents the <code>configEpoch</code> of its master the last time they exchanged packets. This allows other instances to detect when a slave has an old configuration that needs to be updated (Master nodes will not grant votes to slaves with an old configuration).</p> -->
        
        <p>每次由于一些已知节点的值比自己的值大而更新 <code>configEpoch</code> 值，它都会永久性地存储在 nodes.conf 文件中。</p>
        <!-- <p>Every time the <code>configEpoch</code> changes for some known node, it is permanently stored in the nodes.conf file.</p> -->
        
        <p>当一个节点重启，它的 <code>configEpoch</code> 值被设为所有已知节点中最大的那个 <code>configEpoch</code> 值。</p>
        <!-- <p>When a node is restarted its <code>currentEpoch</code> is set to the greatest <code>configEpoch</code> of the known nodes.</p> -->
        
        <h2>丛节点的选举和提升</h2>
        <!-- <h2>Slave election and promotion</h2> -->
        
        <p>从节点的选举和提升都是由从节点处理的，主节点会投票要提升哪个从节点。一个从节点的选举是在主节点被至少一个具有成为主节点必备条件的从节点标记为 <code>FAIL</code> 的状态的时候发生的。</p>
        <!-- <p>Slave election and promotion is handled by slave nodes, with the help of master nodes that vote for the slave to promote.
        A slave election happens when a master is in <code>FAIL</code> state from the point of view of at least one of its slaves that has the prerequisites in order to become a master.</p> -- >
        
        <p>一个从节点为了被提升为主节点，它要开始并且赢得选举。某个给定的主节点的所有从节点都能在主节点为 <code>FAIL</code> 状态的时候发起选举，但是只有一个从节点会赢得选举并被提升为主节点。</p>
        <!-- <p>In order for a slave to promote itself to master, it requires to start an election and win it. All the slaves for a given master can start an election if the master is in <code>FAIL</code> state, however only one slave will win the election and promote itself to master.</p> -->
        
        <p>当以下条件满足时，一个从节点可以发起选举：</p>
        <!-- <p>A slave starts an election when the following conditions are met:</p> -->
        
        <ul>
        <li>该从节点的主节点处于 <code>FAIL</code> 状态。</li>
        <!-- <li>The slave&#39;s master is in <code>FAIL</code> state.</li> -->
        <li>这个主节点负责的哈希槽数目不为零。</li>
        <!-- <li>The master was serving a non-zero number of slots.</li> -->
        <li>从节点和主节点之间的重复连接（replication link）断线不超过一段给定的时间，这是为了确保从节点的数据是可靠的。</li>
        <!-- <li>The slave replication link was disconnected from the master for no longer than a given amount of time, in order to ensure to promote a slave with a reasonable data freshness.</li> -->
        </ul>
        
        <p>一个从节点想要被推选出来，那么第一步应该是提高它的 <code>currentEpoch</code> 计数，并且向主节点们请求投票。</p>
        <!-- <p>In order to be elected the first step for a slave is to increment its <code>currentEpoch</code> counter, and request votes from master instances.</p> -->
        
        <p>从节点通过广播一个 <code>FAILOVER_AUTH_REQUEST</code> 数据包给集群里的每个主节点来请求选票。然后等待回复（最多等 <code>NODE_TIMEOUT</code> 这么长时间）。一旦一个主节点给这个从节点投票，会回复一个 <code>FAILOVER_AUTH_ACK</code>，并且在 <code>NODE_TIMEOUT * 2</code> 这段时间内不能再给同个主节点的其他从节点投票。在这段时间内它完全不能回复其他授权请求。</p>
        <!-- <p>Votes are requested by the slave by broadcasting a <code>FAILOVER_AUTH_REQUEST</code> packet to every master node of the cluster.
        Then it waits for replies to arrive for a maximum time of <code>NODE_TIMEOUT</code>.
        Once a master voted for a given slave, replying positively with a <code>FAILOVER_AUTH_ACK</code>, it can no longer vote for another slave of the same master for a period of <code>NODE_TIMEOUT * 2</code>. In this period it will not be able to reply to other authorization requests at all.</p> -->
      
        <p>从节点会忽视所有带有的时期（epoch）参数比 <code>currentEpoch</code> 小的回应（ACKs），这样能避免把之前的投票的算为当前的合理投票。</p>  
        <!-- <p>The slave will discard all the ACKs that are received having an epoch that is less than the <code>currentEpoch</code>, in order to never count as valid votes that are about a previous election.</p> -->
        
        <p>一旦某个从节点收到了大多数主节点的回应，那么它就赢得了选举。否则，如果无法在 <code>NODE_TIMEOUT</code> 时间内访问到大多数主节点，那么当前选举会被中断并在 <code>NODE_TIMEOUT * 4</code> 这段时间后由另一个从节点尝试发起选举。</p>
        <!-- <p>Once the slave receives ACKs from the majority of masters, it wins the election.
        Otherwise if the majority is not reached within the period of the <code>NODE_TIMEOUT</code>, the election is aborted and a new one will be tried again after <code>NODE_TIMEOUT * 4</code>.</p> -->
        
        <p>从节点并不是在主节点一进入 <code>FAIL</code> 状态就马上尝试发起选举，而是有一点点延迟，这段延迟是这么计算的：</p>
        <!-- <p>A slave does not try to get elected as soon as the master is in <code>FAIL</code> state, but there is a little delay, that is computed as:</p> -->
        
        <pre><code>DELAY = fixed_delay + (data_age - NODE_TIMEOUT) / 10 + 0到2000毫秒之间的随机数。&#x000A;</code></pre>
        <!-- <pre><code>DELAY = fixed_delay + (data_age - NODE_TIMEOUT) / 10 + random delay between 0 and 2000 milliseconds.&#x000A;</code></pre> -->
        
        <p>固定延时（fixed delay）确保我们会等到 <code>FAIL</code> 状态在集群内广播后，否则若从节点尝试发起选举，主节点们仍然不知道那个主节点已经 <code>FAIL</code>，就会拒绝投票。</p>
        <!-- <p>The fixed delay ensures that we wait for the <code>FAIL</code> state to propagate across the cluster, otherwise the slave may try to get elected when the masters are still not away of the <code>FAIL</code> state, refusing to grant their vote.</p> -->
        
        <p><code>data_age / 10</code> 参数是用来让从节点有时间去获得新鲜数据（在与主节点断线的这一小段时间内）。
        随机延时（random delay）是用来添加一些不确定因素以减少多个从节点在同一时间发起选举的可能性，因为若同时多个从节点发起选举或许会导致没有任何节点赢得选举，要再次发起另一个选举的话会使集群在当时变得不可用。</p>
        <!-- <p>The <code>data_age / 10</code> figure is used in order to give an advantage to slaves with fresher data (disconnected from the master for a smaller period of time).
        The random delay is used in order to add some non-determinism that makes less likely that multiple slaves start the election at the same time, a situation that may result into no slave winning the election, requiring another election that makes the cluster not available in the meantime.</p> -->
        
        <p>一旦有从节点赢得选举，它就会开始用 ping 和 pong 数据包向其他节点宣布自己已经是主节点，并提供它负责的哈希槽，设置 <code>configEpoch</code> 为 <code>currentEpoch</code>（选举开始时生成的）。</p>
        <!-- <p>Once a slave wins the election, it starts advertising itself as master in ping and pong packets, providing the set of served slots with a <code>configEpoch</code> set to the <code>currentEpoch</code> at which the election was started.</p> -->
        
        <p>为了加速其他节点的重新配置，该节点会广播一个 pong 包 给集群里的所有节点（那些现在访问不到的节点最终也会收到一个 ping 包或 pong 包，并且进行重新配置）。</p>
        <!-- <p>In order to speedup the reconfiguration of other nodes, a pong packet is broadcasted to all the nodes of the cluster (however nodes not currently reachable will eventually receive a ping or pong packet and will be reconfigured).</p> -->
        
        <p>其他节点会检测到有一个新的主节点（带着更大的<code>configEpoch</code>）在负责处理之前一个旧的主节点负责的哈希槽，然后就升级自己的配置信息。
        旧主节点的从节点，或者是经过故障转移后重新加入集群的该旧主节点，不仅会升级配置信息，还会配置新主节点的备份。</p>
        <!-- <p>The other nodes will detect that there is a new master serving the same slots served by the old master but with a greater <code>configEpoch</code>, and will upgrade the configuration. Slaves of the old master, or the failed over master that rejoins the cluster, will not just upgrade the configuration but will also configure to replicate from the new master.</p> -->
        
        <h2>主节点回复从节点的投票请求</h2>
        <!-- <h2>Masters reply to slave vote request</h2> -->
        
        <p>在上一节中我们讨论了从节点是如何被选举上的，这一节我们将从主节点的角度解释在为给定从节点投票的时候发生了什么。</p>
        <!-- <p>In the previous section it was discussed how slaves try to get elected, this section explains what happens from the point of view of a master that is requested to vote for a given slave.</p> -->
        
        <p>主节点接收到来自于从节点、要求以 <code>FAILOVER_AUTH_REQUEST</code> 请求的形式投票的请求。</p>
        <!-- <p>Masters receive requests for votes in form of <code>FAILOVER_AUTH_REQUEST</code> requests from slaves.</p> -->
        
        <p>要授予一个投票，必须要满足以下条件：</p>
        <!-- <p>For a vote to be granted the following conditions need to be met:</p> -->
        
        <ul>
        <li>1) 在一个给定的时段（epoch）里，一个主节点只能投一次票，并且拒绝给以前时段投票：每个主节点都有一个 lastVoteEpoch 域，一旦认证请求数据包（auth request packet）里的 <code>currentEpoch</code> 小于 lastVoteEpoch，那么主节点就会拒绝再次投票。当一个主节点积极响应一个投票请求，那么 lastVoteEpoch 会相应地进行更新。</li>
        <!-- <li>1) A master only votes a single time for a given epoch, and refuses to vote for older epochs: every master has a lastVoteEpoch field and will refuse to vote again as long as the <code>currentEpoch</code> in the auth request packet is not greater than the lastVoteEpoch. When a master replies positively to an vote request, the lastVoteEpoch is updated accordingly.</li> -->
        <li>2) 一个主节点投票给某个从节点当且仅当该从节点的主节点被标记为 <code>FAIL</code>。</li>
        <!-- <li>2) A master votes for a slave only if the slave&#39;s master is flagged as <code>FAIL</code>.</li> -->
        <li>3) 如果认证请求里的 <code>currentEpoch</code> 小于主节点里的 <code>currentEpoch</code> 的话，那么该请求会被忽视掉。因此，主节点的回应总是带着和认证请求一致的 <code>currentEpoch</code>。如果同一个从节点在增加 <code>currentEpoch</code> 后再次请求投票，那么保证一个来自于主节点的、旧的延迟回复不会被新一轮选举接受。</li>
        <!-- <li>3) Auth requests with a <code>currentEpoch</code> that is less than the master <code>currentEpoch</code> are ignored. Because of this the Master reply will always have the same <code>currentEpoch</code> as the auth request. If the same slave asks again to be voted, incrementing the <code>currentEpoch</code>, it is guaranteed that an old delayed reply from the master can not be accepted for the new vote.</li> -->
        </ul>
        
        <p>下面的例子是没有依据这个规则引发的事件：</p>
        <!-- <p>Example of the issue caused by not using this rule:</p> -->
        
        <p>主节点的 <code>currentEpoch</code> 是 5， lastVoteEpoch 是 1（在几次失败的选举后这也许会发生的）</p>
        <!-- <p>Master <code>currentEpoch</code> is 5, lastVoteEpoch is 1 (this may happen after a few failed elections)</p> -->
        
        <ul>
        <li>从节点的 <code>currentEpoch</code> 是 3。</li>
        <!-- <li>Slave <code>currentEpoch</code> is 3</li> -->
        <li>从节点尝试用 epoch 值为 4（3+1）来赢得选票，主节点回复 ok，里面的 <code>currentEpoch</code> 是 5，可是这个回复延迟了。</li>
        <!-- <li>Slave tries to be elected with epoch 4 (3+1), master replies with an ok with <code>currentEpoch</code> 5, however the reply is delayed.</li> -->
        <li>从节点尝试用 epoch 值为 5（4+1）来再次赢得选票，收到的是带着 <code>currentEpoch</code> 值为 5 的延迟回复，这个回复会被当作有效的来接收。</li>
        <!-- <li><p>Slave tries to be elected again, with epoch 5 (4+1), the delayed reply reaches the master with <code>currentEpoch</code> 5, and is accepted as valid.</p></li> -->
        <li><p>4) 主节点若已经为某个失效主节点的一个从节点投票后，在经过 <code>NODE_TIMEOUT * 2</code> 时间之前不会为同个失效主节点的另一个从节点投票。这并不是严格要求的，因为两个从节点用同个 epoch 来赢得选举的可能性很低，不过在实际中，系统确保正常情况当一个从节点被选举上，那么它有足够的时间来通知其他从节点，以避免另一个从节点发起另一个新的选举。</p></li>
        <!-- <li><p>4) Masters don&#39;t vote a slave of the same master before <code>NODE_TIMEOUT * 2</code> has elapsed since a slave of that master was already voted. This is not strictly required as it is not possible that two slaves win the election in the same epoch, but in practical terms it ensures that normally when a slave is elected it has plenty of time to inform the other slaves avoiding that another slave will try a new election.</p></li> -->
        <li><p>5) 主节点不会用任何方式来尝试选出最好的从节点，只要从节点的主节点处于 <code>FAIL</code> 状态并且投票主节点在这一轮中还没投票，主节点就能进行积极投票。</p></li>
        <!-- <li><p>5) Masters don&#39;t try to select the best slave in any way, simply if the slave&#39;s master is in <code>FAIL</code> state and the master did not voted in the current term, the positive vote is granted.</p></li> -->
        <li><p>6) 若一个主节点拒绝为给定从节点投票，它不会给任何负面的回应，只是单纯忽略掉这个投票请求。</p></li>
        <!-- <li><p>6) When a master refuses to vote for a given slave there is no negative response, the request is simply ignored.</p></li> -->
        <li></p>7) 主节点不会授予投票给那些 <code>configEpoch</code> 值比主节点哈希槽表里的 <code>configEpoch</code> 更小的从节点。记住，从节点发送了它的主节点的 <code>configEpoch</code> 值，还有它的主节点负责的哈希槽对应的位图。本质上来说，这意味着，请求投票的从节点必须拥有它想要进行故障转移的哈希槽的配置信息，而且信息应该比它请求投票的主节点的配置信息更新或者一致。</p></li>
        <!-- <li><p>7) Masters don&#39;t grant the vote to slaves sending a <code>configEpoch</code> that is less than any <code>configEpoch</code> in the master table for the slots claimed by the slave. Remember that the slave sends the <code>configEpoch</code> of its master, and the bitmap of the slots served by its master. What this means is basically that the slave requesting the vote must have a configuration, for the slots it wants to failover, that is newer or equal the one of the master granting the vote.</p></li> -->
        </ul>
        
        <h2>从节点选举的竞争情况</h2>
        <!-- <h2>Race conditions during slaves election</h2> -->
        
        <p>这一节解释如何使用 epoch 概念来使得从节点提升过程对分区操作更有抵抗力。</p>
        <!-- <p>This section illustrates how the concept of epoch is used to make the slave promotion process more resistant to partitions.</p> -->
        
        <ul>
        <li>主节点不是无限期地可达。它拥有三个从节点 A，B，C。</li>
        <!-- <li>A master is no longer reachable indefinitely. The master has three slaves A, B, C.</li> -->
        <li>从节点 A 赢得了选举并且被推选为主节点。</li>
        <!-- <li>Slave A wins the election and is promoted as master.</li> -->
        <li>一个分区操作使得集群中的大多数节点无法访问节点 A。</li>
        <!-- <li>A partition makes A not available for the majority of the cluster.</li> -->
        <li>节点 B 赢得了选举并且被推选为主节点。</li>
        <!-- <li>Slave B wins the election and is promoted as master.</li> -->
        <li>一个分区操作使得集群中大多数节点无法访问节点 B。</li>
        <!-- <li>A partition makes B not available for the majority of the cluster.</li> -->
        <li>之前分区操作的问题被修复了，节点 A 又恢复可访问状态。</li>
        <!-- <li>The previous partition is fixed, and A is available again.</li> -->
        </ul>
        
        <p>此刻，节点 B 仍然失效，节点 A 恢复可访问，会与节点 C 竞选去获得选票对节点 B 进行故障转移。</p>
        <!-- <p>At this point B is down, and A is available again and will compete with C that will try to get elected in order to fail over B.</p> -->
        
        <p>这两个有同样的哈希槽的从节点最终都会请求被提升，然而由于它们发布的 <code>configEpoch</code> 是不一样的，而且节点 C 的 epoch 比较大，所以所有的节点都会把它们的配置更新为节点 C 的。</p>
        <!-- <p>Both will eventually claim to be promoted slaves for the same set of hash slots, however the <code>configEpoch</code> they publish will be different, and the C epoch will be greater, so all the other nodes will upgrade their configuration to C.</p> -->
        
        <p>节点 A 会从来源于节点 C（负责同样哈希槽的节点）的 ping 包中检测出节点 C 的 epoch 是更大的，所以它会重新设置自己为节点 C 的一个从节点。</p>
        <!-- <p>A itself will detect pings from C serving the same slots with a greater epoch and will reconfigure as a slave of C.</p> -->
        
        <h2>服务器哈希槽信息的传播规则</h2>
        <!-- <h2>Rules for server slots information propagation</h2> -->
        
        <p>Redis 集群很重要的一个部分是用来传播关于集群节点负责哪些哈希槽的信息的机制。这对于新集群的启动和提升从节点来负责处理哈希槽（它那失效的主节点本该处理的槽）的能力来说是必不可少的。</p>
        <!-- <p>An important part of Redis Cluster is the mechanism used to propagate the information about which cluster node is serving a given set of hash slots. This is vital to both the startup of a fresh cluster and the ability to upgrade the configuration after a slave was promoted to serve the slots of its failing master.</p> -->
        
        <p>个体持续交流使用的 ping 包和 pong 包都包含着一个头部，这个头部是给发送者使用的，为了向别的节点宣传它负责的哈希槽。这是主要用来传播变更的机制，不过集群管理员手动进行重新配置是例外（比如为了在主节点间移动哈希槽，通过 redis-trib 来进行手动碎片整理）。</p>
        <!-- <p>Ping and Pong packets that instances continuously exchange contain an header that is used by the sender in order to advertise the hash slots it claims to be responsible for. This is the main mechanism used in order to propagate change, with the exception of a manual reconfiguration operated by the cluster administrator (for example a manual resharding via redis-trib in order to move hash slots among masters).</p> -->
   
        <p>当一个新的 Redis 集群节点创建的时候，它的本地哈希槽表（表示给定哈希槽和给定节点 ID 的映射关系表）被初始化，每个哈希槽被置为 nil，也就是，每个哈希槽都是没赋值的。</p>
        <!-- <p>When a new Redis Cluster node is created, its local slot table, that maps a given hash slot with a given node ID, is initialized so that every hash slot is assigned to nil, that is, the hash slot is unassigned.</p> -->
        
        <p>一个节点要更新它的哈希槽表所要遵守的第一个规则如下：</p>
        <!-- <p>The first rule followed by a node in order to update its hash slot table is the following:</p> -->
        
        <p><strong>规则 1：如果一个哈希槽是没有赋值的，然后有个已知节点认领它，那么我就会修改我的哈希槽表，把这个哈希槽和这个节点关联起来。</strong></p>
        <!-- <p><strong>Rule 1: If an hash slot is unassigned, and a known node claims it, I&#39;ll modify my hash slot table to associate the hash slot to this node.</strong></p> -->
        
        <p>由于这个规则，当一个新集群被创建的时候，只需要手动给哈希槽赋值上（通常是通过 redis-trib 命令行工具使用 <code>CLUSTER</code> 命令来实现）负责它的主节点，然后这些信息就会迅速在集群中传播开来。</p>
        <!-- <p>Because of this rule, when a new cluster is created, it is only needed to manually assign (using the <code>CLUSTER</code> command, usually via the redis-trib command line tool) the slots served by each master node to the node itself, and the information will rapidly propagate across the cluster.</p> -->
        
        <p>然而，当一个配置更新的发生是因为一个从节点在其主节点失效后被提升为主节点的时候，这个规则显然还不足够。新的主节点会宣传之前它做从节点的时候负责的哈希槽，但从其他节点看来这些哈希槽并没有被重新赋值，所以如果它们只遵守第一个规则的话就不会升级配置信息。</p>
        <!-- <p>However this rule is not enough when a configuration update happens because of a slave gets promoted to master after a master failure. The new master instance will advertise the slots previously served by the old slave, but those slots are not unassigned from the point of view of the other nodes, that will not upgrade the configuration if they just follow the first rule.</p> -->
        
        <p>由于这个原因就有第二个规则，是用来把一个已赋值给以前节点的哈希槽重新绑定到一个新的认领它的节点上。规则如下：</p>
        <!-- <p>For this reason there is a second rule that is used in order to rebind an hash slot already assigned to a previous node to a new node claiming it. The rule is the following:</p> -->
        
        <p><strong>规则 2：如果一个哈希槽已经被赋值了，有个节点它的 <code>configEpoch</code> 比哈希槽当前拥有者的值更大，并且该节点宣称正在负责该哈希槽，那么我们会把这个哈希槽重新绑定到这个新节点上。</strong></p>
        <!-- <p><strong>Rule 2: If an hash slot is already assigned, and a known node is advertising it using a <code>configEpoch</code> that is greater than the <code>configEpoch</code> advertised by the current owner of the slot, I&#39;ll rebind the hash slot to the new node.</strong></p> -->
        
        <p>因为有这第二个规则，所以集群中的所有节点最终都会同意哈希槽的拥有者是所有声称拥有它的节点中 <code>configEpoch</code> 值最大的那个。</p>
        <!-- <p>Because of the second rule eventually all the nodes in the cluster will agree that the owner of a slot is the one with the greatest <code>configEpoch</code> among the nodes advertising it.</p> -->
        
        <h1>UPDATE 消息</h1>
        <!-- <h1>UPDATE messages</h1> -->
        
        <p>上面描述的传播哈希槽配置信息的系统只使用节点间交换信息的普通 ping 包和 pong 包。</p>
        <!-- <p>The described system for the propagation of hash slots configurations
        only uses the normal ping and pong messages exchanged by nodes.</p> -->
        
        <p>这要求存在一个节点（可以是负责给定哈希槽的主节点或从节点）拥有更新后的配置信息，因为节点是在 ping 包和 pong 包头部中发送它们自己的配置信息。</p>
        <!-- <p>It also requires that there is a node that is either a slave or a master
        for a given hash slot and has the updated configuration, because nodes
        send their own configuration in ping and pong packets headers.</p> -->
        
        <p>然而也存在例外。当有一个节点，它是唯一一个负责处理给定哈希槽的节点，有可能在分区操作后它恢复正常，但拥有的配置信息是过时的。</p>
        <!-- <p>However sometimes a node may recover after a partition in a setup where
        it is the only node serving a given hash slot, but with an old configuration.</p> -->
        
        <p>例子：一个给定的哈希槽是由节点 A 和 B 负责的。节点 A 是一个主节点，然后它在某个时刻失效了，所以节点 B 被提升为主节点。过了一段时间节点 B 也失效了，集群没有其他备份节点可以来处理这个哈希槽，所以只能开始修复操作。</p>
        <!-- <p>Example: a given hash slot is served by node A and B. A is the master, and at some point fails, so B is promoted as master. Later B fails as well, and the cluster has no way to recover since there are no more replicas for this hash slot.</p> -->
        
        <p>在一段时间过后节点 A 恢复正常了，并且作为一个可写入的主节点重新加入集群，但它的配置信息是过时的。此时没有任何备份节点能更新它的配置信息。这就是 UPDATE 消息存在的目的：当一个节点检测到其他节点在宣传它的哈希槽的时候是用一份过时的配置信息，那么它就会向这个节点发送一个 UPDATE 消息，这个消息包含新节点的 ID 和它负责的哈希槽（以 bitmap 形式发送）。</p>
        <!-- <p>However A may recover some time later, and rejoin the cluster with an old configuration in which it was writable as a master. There is no replica that can update its configuration. This is the goal of UPDATE messages: when a node detects that another node is advertising its hash slots with an old configuration, it sends the node an UPDATE message with the ID of the new node serving the slots and the set of hash slots (send as a bitmap) that it is serving.</p> -->
        
        <p>注意：目前更新配置信息可以用 ping 包/ pong 包，也可以用 UPDATE 消息，这两种方法是共享同一个代码路径（code path）。这两者在更新一个带有老旧信息的节点的配置信息时会有功能上的重复。然而这两种机制都是非常有用的，因为 ping / pong 包在一段时间后能填充（populate）新节点的哈希槽路由表，而 UPDATE 消息只是在一个过时配置信息被检测出来时才被发送出去，并且只覆盖那些需要修复的错误配置信息。</p>
        <!-- <p>NOTE: while currently configuration updates via ping / pong and UPDATE share the
        same code path, there is a functional overlap between the two in the way they
        update a configuration of a node with stale information. However the two
        mechanisms are both useful because ping / pong messages after some time are
        able to populate the hash slots routing table of a new node, while UPDATE
        messages are only sent when an old configuration is detected, and only
        cover the information needed to fix the wrong configuration.</p> -->
        
        <h2>备份迁移</h2>
        <!-- <h2>Replica migration</h2> -->
        
        <p>Redis 集群实现了一个叫做<em>备份迁移（replica migration）</em>的概念，以提高系统的可用性。在集群中有主节点-从节点的设定，如果主从节点间的映射关系是固定的，那么久而久之，当发生多个单一节点独立故障的时候，系统可用性会变得很有限。</p>
        <!-- <p>Redis Cluster implements a concept called <em>replica migration</em> in order to
        improve the availability of the system. The idea is that in a cluster with
        a master-slave setup, if the map between slaves and masters is fixed there
        is limited availability over time if multiple independent failures of single
        nodes happen.</p> -->
        
        <p>例如有一个每个主节点都只有一个从节点的集群，当主节点或者从节点故障失效的时候集群能让操作继续执行下去，但如果主从节点都失效的话就没法让操作继续执行下去。然而这样长期会积累很多由硬件或软件问题引起的单一节点独立故障。例如：</p>
        <!-- <p>For example in a cluster where every master has a single slave, the cluster
        can continue the operations as long the master or the slave fail, but not
        if both fail the same time. However there is a class of failures, that are
        the independent failures of single nodes caused by hardware or software issues
        that can accumulate over time. For example:</p> -->
        
        <ul>
        <li>主节点 A 有且只有一个从节点 A1。</li>
        <!-- <li>Master A has a single slave A1.</li> -->
        <li>主节点 A 失效了。A1 被提升为新的主节点。</li>
        <!-- <li>Master A fails. A1 is promoted as new slave.</li> -->
        <li>三个小时后，A1 因为一个独立事件（跟节点 A 的失效无关）失效了。由于没有其他从节点可以提升为主节点（因为节点 A 仍未恢复正常），集群没法继续进行正常操作。</li>
        <!-- <li>Three hours later A1 fails in an independent manner (not related to the failure of A). No other slave is available for promotion since also node A is still down. The cluster cannot continue normal operations.</li> -->
        </ul>
        
        <p>如果主从节点间的映射关系是固定的，那要让集群更有抵抗力地面对上面的情况的唯一方法就是为每个主节点添加从节点。然而这要付出的代价也更昂贵，因为要求 Redis 执行更多的实例、更多的内存等等。</p>
        <!-- <p>If the map between masters and slaves is fixed, the only way to make the cluster
        more resistant to the above scenario is to add slaves to every master, however
        this is costly as it requires more instances of Redis to be executed, more
        memory, and so forth.</p> -->
        
        <p>一个候选方案就是在集群中创建不对称性，然后让集群布局时不时地自动变化。例如，假设集群有三个主节点 A，B，C。节点 A 和 B 都各有一个从节点，A1 和 B1。节点 C 有两个从节点：C1 和 C2。</p>
        <!-- <p>An alternative is to create an asymmetry in the cluster, and let the cluster
        layout automatically change over time. For example the cluster may have three
        masters A, B, C. A and B have a single slave each, A1 and B1. However the master
        C is different and has two slaves: C1 and C2.</p> -->
        
        <p>备份迁移是从节点自动重构的过程，为了<em>迁移</em>到一个没有可工作从节点的主节点上。在上面提到的例子中，备份迁移过程如下：</p>
        <!-- <p>Replica migration is the process of automatic reconfiguration of a slave
        in order to <em>migrate</em> to a master that has no longer coverage (no working
        slaves). With replica migration the scenario mentioned above turns into the
        following:</p> -->
        
        <ul>
        <li>主节点 A 失效。A1 被提升为主节点。</li>
        <!-- <li>Master A fails. A1 is promoted.</li> -->
        <li>节点 C2 迁移成为节点 A1 的从节点，要不然 A1 就没有任何从节点。</li>
        <!-- <li>C2 migrates as slave of A1, that is otherwise not backed by any slave.</li> -->
        <li>三个小时后节点 A1 也失效了。</li>
        <!-- <li>Three hours later A1 fails as well.</li> -->
        <li>节点 C2 被提升为取代 A1 的新主节点。</li>
        <!-- <li>C2 is promoted as new master to replace A1.</li> -->
        <li>集群仍然能继续正常工作。</li>
        <!-- <li>The cluster can continue the operations.</li> -->
        </ul>
        
        <h2>备份迁移算法</h2>
        <!-- <h2>Replica migration algorithm</h2> -->
        
        <p>迁移算法不用任何形式的协议，因为 Redis 集群中的从节点布局不是集群配置信息（配置信息要求前后一致并且/或者用 config epochs 来标记版本号）的一部分。
        它使用的是一个避免在主节点没有备份时从节点大批迁移的算法。这个算法保证，一旦集群配置信息稳定下来，最终每个主节点都至少会有一个从节点作为备份。</p>
        <!-- <p>The migration algorithm does not use any form of agreement, since the slaves
        layout in a Redis Cluster is not part of the cluster configuration that requires
        to be consistent and/or versioned with config epochs. Instead it uses an
        algorithm to avoid mass-migration of slaves when a master is not backed.
        The algorithm guarantees that eventually, once the cluster configuration is
        stable, every master will be backed by at least one slave.</p> -->
        
        <p>接下来讲这个算法是如何工作的。在开始之前我们需要定义清楚在这个上下文中什么才算是一个<em>好的从节点</em>：一个好的从节点是指从给定节点的角度看，该从节点不处于 FAIL 状态。</p>
        <!-- <p>This is how the algorithm works. To start we need to define what is a
        <em>good slave</em> in this context: a good slave is a slave not in FAIL state
        from the point of view of a given node.</p> -->
        
        <p>每个从节点若检测出存在至少一个没有好的从节点的单一主节点，那么就会触发这个算法的执行。然而在所有检测出这种情况的从节点中，只有一部分从节点会采取行动。
        通常这“一部分从节点”都只有一个，除非有不同的从节点在给定时间间隔里对其他节点的失效状态有稍微不同的视角。</p>
        <!-- <p>The execution of the algorithm is triggered in every slave that detects that
        there is at least a single master without good slaves. However among all the
        slaves detecting this condition, only a subset should act. This subset is
        actually often a single slave unless different slaves have in a given moment
        a slightly different vision of the failure state of other nodes.</p> -->
        
        <p><em>采取行动的从节点</em>是属于那些拥有最多从节点的主节点，并且不处于 FAIL 状态及拥有最小的节点 ID。</p>
        <!-- <p>The <em>acting slave</em> is the slave among the masters having the maximum number
        of attached slaves, that is not in FAIL state and has the smallest node ID.</p> -->
        
        <p>例如，如果有 10 个主节点，它们各有 1 个从节点，另外还有 2 个主节点，它们各有 5 个从节点。会尝试迁移的从节点是在那 2 个拥有 5 个从节点的主节点中的所有从节点里，节点 ID 最小的那个。已知不需要用到任何协议，在集群配置信息不稳定的情况下，有可能发生一种竞争情况：多个从节点都认为自己是不处于 FAIL 状态并且拥有较小节点 ID（实际上这是一种比较难出现的状况）。如果这种情况发生的话，结果是多个从节点都会迁移到同个主节点下，不过这种结局是无害的。这种竞争发生的话，有时候会使得割让出从节点的主节点变成没有任何备份节点，当集群再次达到稳定状态的时候，本算法会再次执行，然后把从节点迁移回它原来的主节点。</p>
        <!-- <p>So for example if there are 10 masters with 1 slave each, and 2 masters with
        5 slaves each, the slave that will try to migrate is, among the 2 masters
        having 5 slaves, the one with the lowest node ID. Given that no agreement
        is used, it is possible that when the cluster configuration is not stable,
        a race condition occurs where multiple slaves think to be the non-failing
        slave with the lower node ID (but it is an hard to trigger condition in
        practice). If this happens, the result is multiple slaves migrating to the
        same master, which is harmless. If the race happens in a way that will left
        the ceding master without slaves, as soon as the cluster is stable again
        the algorithm will be re-executed again and will migrate the slave back to
        the original master.</p> -->
        
        <p>最终每个主节点都会至少有一个从节点作为备份节点。通常表现出来的行为是，一个从节点从一个拥有多个从节点的主节点迁移到一个孤立的主节点。</p>
        <!-- <p>Eventually every master will be backed by at least one slave, however
        normally the behavior is that a single slave migrates from a master with
        multiple slaves to an orphaned master.</p> -->
        
        <p>这个算法能通过一个用户可配置的参数 <code>cluster-migration-barrier</code> 进行控制。这个参数表示的是，一个主节点在拥有多少个好的从节点的时候就要割让一个从节点出来。例如这个参数若被设为 2，那么只有当一个主节点拥有 2 个可工作的从节点时，它的一个从节点会尝试迁移。</p>
        <!-- <p>The algorithm is controlled by an user-configurable parameter called
        <code>cluster-migration-barrier</code>, that is the number of good slaves a master
        will be left with for a slave to migrate. So for example if this parameter
        is set to 2, a slave will try to migrate only if its master remains with
        two working slaves.</p> -->
        
        <h1>发布/订阅（Publish/Subscribe）</h1>
        <!-- <h1>Publish/Subscribe</h1> -->
        
        <p>在一个 Redis 集群中，客户端能订阅任何一个节点，也能发布消息给任何一个节点。集群会确保发布的消息都会按需进行转发。</p>
        <!-- <p>In a Redis Cluster clients can subscribe to every node, and can also
        publish to every other node. The cluster will make sure that publish
        messages are forwarded as needed.</p> -->
        
        <p>目前的实现方式是单纯地向所有节点广播所有的发布消息，在将来的实现中会用 bloom filters 或其他算法来优化。</p>
        <!-- <p>The current implementation will simply broadcast all the publish messages
        to all the other nodes, but at some point this will be optimized either
        using bloom filters or other algorithms.</p> -->
        
        <h2>附录 A：CRC16算法的 ANSI C 版本的参考实现</h2>
        <!-- <h2>Appendix A: CRC16 reference implementation in ANSI C</h2> -->
        
        <pre><code>/*&#x000A; * Copyright 2001-2010 Georges Menie (www.menie.org)&#x000A; * Copyright 2010 Salvatore Sanfilippo (adapted to Redis coding style)&#x000A; * All rights reserved.&#x000A; * Redistribution and use in source and binary forms, with or without&#x000A; * modification, are permitted provided that the following conditions are met:&#x000A; *&#x000A; *     * Redistributions of source code must retain the above copyright&#x000A; *       notice, this list of conditions and the following disclaimer.&#x000A; *     * Redistributions in binary form must reproduce the above copyright&#x000A; *       notice, this list of conditions and the following disclaimer in the&#x000A; *       documentation and/or other materials provided with the distribution.&#x000A; *     * Neither the name of the University of California, Berkeley nor the&#x000A; *       names of its contributors may be used to endorse or promote products&#x000A; *       derived from this software without specific prior written permission.&#x000A; *&#x000A; * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS&#39;&#39; AND ANY&#x000A; * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED&#x000A; * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE&#x000A; * DISCLAIMED. IN NO EVENT SHALL THE REGENTS AND CONTRIBUTORS BE LIABLE FOR ANY&#x000A; * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES&#x000A; * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;&#x000A; * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND&#x000A; * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT&#x000A; * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS&#x000A; * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.&#x000A; */&#x000A;&#x000A;/* CRC16 implementation according to CCITT standards.&#x000A; *&#x000A; * Note by @antirez: this is actually the XMODEM CRC 16 algorithm, using the&#x000A; * following parameters:&#x000A; *&#x000A; * Name                       : &quot;XMODEM&quot;, also known as &quot;ZMODEM&quot;, &quot;CRC-16/ACORN&quot;&#x000A; * Width                      : 16 bit&#x000A; * Poly                       : 1021 (That is actually x^16 + x^12 + x^5 + 1)&#x000A; * Initialization             : 0000&#x000A; * Reflect Input byte         : False&#x000A; * Reflect Output CRC         : False&#x000A; * Xor constant to output CRC : 0000&#x000A; * Output for &quot;123456789&quot;     : 31C3&#x000A; */&#x000A;&#x000A;static const uint16_t crc16tab[256]= {&#x000A;    0x0000,0x1021,0x2042,0x3063,0x4084,0x50a5,0x60c6,0x70e7,&#x000A;    0x8108,0x9129,0xa14a,0xb16b,0xc18c,0xd1ad,0xe1ce,0xf1ef,&#x000A;    0x1231,0x0210,0x3273,0x2252,0x52b5,0x4294,0x72f7,0x62d6,&#x000A;    0x9339,0x8318,0xb37b,0xa35a,0xd3bd,0xc39c,0xf3ff,0xe3de,&#x000A;    0x2462,0x3443,0x0420,0x1401,0x64e6,0x74c7,0x44a4,0x5485,&#x000A;    0xa56a,0xb54b,0x8528,0x9509,0xe5ee,0xf5cf,0xc5ac,0xd58d,&#x000A;    0x3653,0x2672,0x1611,0x0630,0x76d7,0x66f6,0x5695,0x46b4,&#x000A;    0xb75b,0xa77a,0x9719,0x8738,0xf7df,0xe7fe,0xd79d,0xc7bc,&#x000A;    0x48c4,0x58e5,0x6886,0x78a7,0x0840,0x1861,0x2802,0x3823,&#x000A;    0xc9cc,0xd9ed,0xe98e,0xf9af,0x8948,0x9969,0xa90a,0xb92b,&#x000A;    0x5af5,0x4ad4,0x7ab7,0x6a96,0x1a71,0x0a50,0x3a33,0x2a12,&#x000A;    0xdbfd,0xcbdc,0xfbbf,0xeb9e,0x9b79,0x8b58,0xbb3b,0xab1a,&#x000A;    0x6ca6,0x7c87,0x4ce4,0x5cc5,0x2c22,0x3c03,0x0c60,0x1c41,&#x000A;    0xedae,0xfd8f,0xcdec,0xddcd,0xad2a,0xbd0b,0x8d68,0x9d49,&#x000A;    0x7e97,0x6eb6,0x5ed5,0x4ef4,0x3e13,0x2e32,0x1e51,0x0e70,&#x000A;    0xff9f,0xefbe,0xdfdd,0xcffc,0xbf1b,0xaf3a,0x9f59,0x8f78,&#x000A;    0x9188,0x81a9,0xb1ca,0xa1eb,0xd10c,0xc12d,0xf14e,0xe16f,&#x000A;    0x1080,0x00a1,0x30c2,0x20e3,0x5004,0x4025,0x7046,0x6067,&#x000A;    0x83b9,0x9398,0xa3fb,0xb3da,0xc33d,0xd31c,0xe37f,0xf35e,&#x000A;    0x02b1,0x1290,0x22f3,0x32d2,0x4235,0x5214,0x6277,0x7256,&#x000A;    0xb5ea,0xa5cb,0x95a8,0x8589,0xf56e,0xe54f,0xd52c,0xc50d,&#x000A;    0x34e2,0x24c3,0x14a0,0x0481,0x7466,0x6447,0x5424,0x4405,&#x000A;    0xa7db,0xb7fa,0x8799,0x97b8,0xe75f,0xf77e,0xc71d,0xd73c,&#x000A;    0x26d3,0x36f2,0x0691,0x16b0,0x6657,0x7676,0x4615,0x5634,&#x000A;    0xd94c,0xc96d,0xf90e,0xe92f,0x99c8,0x89e9,0xb98a,0xa9ab,&#x000A;    0x5844,0x4865,0x7806,0x6827,0x18c0,0x08e1,0x3882,0x28a3,&#x000A;    0xcb7d,0xdb5c,0xeb3f,0xfb1e,0x8bf9,0x9bd8,0xabbb,0xbb9a,&#x000A;    0x4a75,0x5a54,0x6a37,0x7a16,0x0af1,0x1ad0,0x2ab3,0x3a92,&#x000A;    0xfd2e,0xed0f,0xdd6c,0xcd4d,0xbdaa,0xad8b,0x9de8,0x8dc9,&#x000A;    0x7c26,0x6c07,0x5c64,0x4c45,0x3ca2,0x2c83,0x1ce0,0x0cc1,&#x000A;    0xef1f,0xff3e,0xcf5d,0xdf7c,0xaf9b,0xbfba,0x8fd9,0x9ff8,&#x000A;    0x6e17,0x7e36,0x4e55,0x5e74,0x2e93,0x3eb2,0x0ed1,0x1ef0&#x000A;};&#x000A;&#x000A;uint16_t crc16(const char *buf, int len) {&#x000A;    int counter;&#x000A;    uint16_t crc = 0;&#x000A;    for (counter = 0; counter &lt; len; counter++)&#x000A;            crc = (crc&lt;&lt;8) ^ crc16tab[((crc&gt;&gt;8) ^ *buf++)&amp;0x00FF];&#x000A;    return crc;&#x000A;}&#x000A;</code></pre>
      </article>
      </div>
    <script src='/js/foot.js'></script>
  </body>
</html>
